* a进制转化为b进制（快捷短除法）

https://www.acwing.com/problem/content/description/126/

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int a,b;
        string a_line,b_line;
        cin>>a>>b>>a_line;
        vector<int> number;
        for(auto t:a_line)     //字符串转数组
        {     
            if(t>='0'&&t<='9')    number.push_back(t-'0');      //'0'~'9'直接转化为0-9
            if(t>='A'&&t<='Z')    number.push_back(t-'A'+10);   //'A'~'Z'转化为10~35
            if(t>='a'&&t<='z')    number.push_back(t-'a'+36);   //'a'~'z'转化为36~62
        }

        reverse(number.begin(),number.end());        //反转number数组 比如1234 变为4321

        vector<int> res;   
        while(number.size())   //****重点****
        {
            int r=0;                //定义r为余数
            for(int i=number.size()-1; i>=0; i--)   //从后往前枚举  4321------->1,2,3,4
            {
                number[i]+=r*a;    //每个被除数都要加上(前一位的余数*a(转化前的进制))
                r=number[i]%b;     //r==number数组除b(需要转化后的进制)得到的余数即是(结果的每一个数)
                number[i]/=b;      //number再去掉已经运算过的位数，即除一次number位数就减少一位
            }             
            res.push_back(r);      //将余数存入res数组
            while(number.size()&&number.back()==0) number.pop_back(); //去掉number数组运算后时的前导0
        }

        reverse(res.begin(),res.end());//根据短除法，需要从后往前读才是需要进制转化后的结果，所以要进行反转

        for(auto x:res)   //枚举整个res数字数组，将其存入b_line字符串中
        {
            if(x>=0&&x<=9)            b_line+=char(x+'0'); //<=9就转化为'9'
            if(x>=10&&x<=35)    b_line+=char(x+'A'-10);    //>=10&&<=35转化为'A'~'Z'
            if(x>=36)           b_line+=char(x+'a'-36);    //>=36就转化为'a'~'z'

        }

        cout<<a<<" "<<a_line<<endl;    //按照题意进行结果输出
        cout<<b<<" "<<b_line<<endl;
        cout<<endl;
    }

    return 0;
}