#include<vector>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;

int main()
{


    int n;
    cin >> n;
    while (n--)
    {
        vector<int> num;
        int a,b;
        string s;
        cin >> a >> b >> s;
        for(int i = s.size() - 1; i >= 0; i--)
        {
            if(s[i] <= '9') num.push_back(s[i] -'0');
            else if(s[i] <= 'Z') num.push_back(s[i] - 'A' + 10);
            else if(s[i] <= 'z') num.push_back(s[i] - 'a' + 36);
        }
        vector<int> res;
        while (num.size())
        {
            int t = 0;
            for(int i = num.size() - 1; i >= 0; i--)
            {
                num[i] += a*t;
                t = num[i] % b;
                num[i] /= b;
            }
            res.push_back(t);
            while (num.size() && num.back() == 0)
            {
                num.pop_back();
            }
        }
        string res_str;
        for(int i = 0; i < res.size(); i++)
        {
            if(res[i] <= 9) res_str.push_back(char(res[i] + '0'));
            else if(res[i] <= 'Z' - 'A' + 10) res_str.push_back( char(res[i] + 'A' - 10));
            else if(res[i] <= 'z' - 'a' + 36) res_str.push_back( char(res[i] + 'a' - 36));
        }
        reverse(res_str.begin(), res_str.end());
        cout << a <<" "<< s << endl;
        cout << b <<" "<< res_str << endl <<endl;

    }




}