#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int a,b;
        string a_line, b_line;
        cin >> a >> b >> a_line;
        // b是将要转换的进制
        vector<int> number;
        for(auto c : a_line)
        {
            if(c >= '0' && c <= '9')    number.push_back(c - '0');
            if(c >= 'A' && c <= 'Z')    number.push_back(c-'A' + 10);
            if(c >= 'a' && c <= 'z')    number.push_back(c -'a' + 36);
        }
        reverse(number.begin(),number.end());

        vector<int> res;
        while(number.size())
        {
            int r = 0;
            for(int i = number.size()-1; i >= 0;i--)
            {
                number[i] += r * a;
                r = number[i] % b;
                number[i] /= b;
            }
            res.push_back(r);
            while(number.size() && number.back()==0) number.pop_back(); // 把前面的0去掉 
        }

        reverse(res.begin(),res.end()); // 求得得进制数
        for(int i = 0;i < res.size();i++)
        {
            int a = res[i];
            if(a >= 0 && a <= 9)    b_line += char(a + '0');
            if(a >= 10 && a <= 35)  b_line += char(a - 10 + 'A');
            if(a >= 36)  b_line += char(a - 36 + 'a');
        }
        cout << a << " "<< a_line<<endl;
        cout << b << " "<<b_line << endl;
        cout << endl;
    }
    return 0;
}