import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;

public class Main{
	
	public static int ff(char c){
		if(c>='0'&&c<='9') return c-'0'; 
        else if(c>='A'&&c<='Z') return c-'A'+10; 
        else if(c>='a'&&c<='z') return c-'a'+36; 
        return 0;
		}
	public static char gg(int i){
		if(i>=0&&i<=9) return (char)('0'+i);
		else if(i>=10&&i<=35) return (char)('A'+i-10);
		else return (char)('a'+i-36);
	}
	public static String rev(String ss){
		
        char[] b=ss.toCharArray();
        char temp;
        for(int i=0;i<b.length/2;i++){
         temp=b[i];
         b[i]=b[b.length-i-1];
         b[b.length-i-1]=temp;
        }
        return new String(b);
     }
		
	public static void main(String[] args){
		
		Scanner cin = new Scanner(System.in);
		
		int len,i;
		BigInteger D,ans,sum,R,T;
		
		int n=cin.nextInt();
		while((n--)!=0){
		    String st,ss;
			R = cin.nextBigInteger();
            T = cin.nextBigInteger();
			st=cin.next();
			len=st.length();
		    ans=BigInteger.ZERO;
			for(i=0;i<len;i++){
			
				D=BigInteger.valueOf(ff(st.charAt(i)));
				ans=ans.multiply(R);
				ans=ans.add(D);
				
				}
		//	ss="";
		    char ch[]=new char[10000];
		    i=0;
			while(ans.compareTo(BigInteger.ZERO)!=0){
              int temp = ans.remainder(T).intValue();
                ans= ans.divide(T);
                char c=gg(temp);
              //  ss=ss+String.valueOf(c);
                ch[i++]=c;
                }
                System.out.print(R+" ");
                System.out.println(st);
                System.out.printf(T+" ");
            //    System.out.println(rev(ss));
                for (int j = i-1; j > 0; j--)
                 System.out.print(ch[j]);
                 System.out.println(ch[0]);
                System.out.print("\n");
			}
		}
	}