Problem Description

集训队最菜的卖女孩的小火柴最近遇到了一个大麻烦.

他读幼儿园的妹妹问了他一题问题：给出一个数n，接着给出两个数a，b（2<=a<=b<=35）.

让你求出a进制的n数转化为a+1进制后的值在转化为a+2进制，然后在转化为a+3进制，直到转化为b进制为止.

大于9的数用大写的ABCD....表示.

数据保证进制每次转化后的数小于10^18.

他太菜了，所以不会，相信各位ACMER大佬们会帮他解答（这么水的题你不帮我写？）.

Input

T组输入

接下来T行，每行一个a进制整数n，两个正整数a,b

(T<=500000,0<=n<=10^18)

Output

对每次输入，输出答案

SampleInput

311 10 12BAD 15 20111111 2 5

SampleOutput

B6BI223 思路：题目要求把n转化为a+1进制，在转a+2进制，直到b进制为止。 如果你按题目的要求来的话，直接tle。 不难发现，你把n转化为a+1进制的时候，是先把a进制转为10进制，然后在转a+1进制，然后从a+1进制转a+2进制，是把a+1进制的数转为10进制，在转a+3. 所以可以直接跳过中间这些，直接把a进制数n转为b进制就OK了. 其中0需要特判，因为0的话没办法转进制，不会输出0. 附上AC部分代码：

x=0;scanf("%s %d %d",&s,&r,&k);for(i=0; s[i]; i++)    if(s[i]>64&&s[i]<91)        x=x*r+s[i]+10-'A';    else        x=x*r+s[i]-'0';if(!x){    puts("0");    continue;}for(i=0; x; i++){    r=x%k;    if(r>9)        s[i]='A'+r-10;    else        s[i]='0'+r;    x/=k;}for(i=i-1; i+1;)    printf("%c",s[i--]);puts("");