import java.math.BigInteger;
import java.util.TreeMap;
import java.util.Scanner;

public class d_joe
{
	public static void main(String args[])
	{
		new d_joe();		

	}

	TreeMap<Integer,Character> valToChar;

	public d_joe()
	{
		valToChar=new TreeMap<Integer,Character>();
		for(char c='0'; c<='9'; c++) { valToChar.put(charToVal(c),c); }
		for(char c='a'; c<='z'; c++) { valToChar.put(charToVal(c),c); }
		for(char c='A'; c<='Z'; c++) { valToChar.put(charToVal(c),c); }

		for(int v : valToChar.keySet())
		{
			//System.out.println("" + v + ": " + valToChar.get(v));
		}

		Scanner scan=new Scanner(System.in);

		int Cases;
		Cases=scan.nextInt();
		for(int cs=0; cs<Cases; cs++)
		{
			int src_base=scan.nextInt();
			int dst_base=scan.nextInt();
			String src_str=scan.next();

			BigInteger src_num=new BigInteger("0");
			for(int i=0; i<src_str.length(); i++)
			{
				char c=src_str.charAt(i);
				int v=charToVal(c);
				src_num = src_num.multiply(new BigInteger("" + src_base));
				src_num = src_num.add(new BigInteger("" + v));
			}
			System.out.println("" + src_base + " " + src_str);
			//System.out.println("10 " + src_num);

			BigInteger n=src_num;
			String dst_str="";
			BigInteger dst_base_i=new BigInteger("" + dst_base);
			while(!n.toString().equals("0"))
			{
				//System.out.println(n);
				BigInteger sub=n.mod(dst_base_i);
				int v=sub.intValue();
				char c=valToChar(v);
				dst_str= "" + c + dst_str;
				n=n.subtract(new BigInteger("" + v)).divide(dst_base_i);
			}
			if (dst_str.length()==0) dst_str="0";
			System.out.println("" + dst_base + " " + dst_str);
			System.out.println("");
		}

	}

	int charToVal(char c)
	{
		if ((c >='0') && (c <= '9'))
		{
			return c - '0';
		}
		if ((c >='A') && (c <= 'Z'))
		{
			return 10 + c -'A';
		}
		if ((c >='a') && (c <= 'z'))
		{
			return 36 + c -'a';
		}
		return -1;
	}

	char valToChar(int v)
	{
		return valToChar.get(v);
	}

	


}