import java.io.*;

 import java.util.*;

 import java.math.*;

 public class Main {

     public static int GetNum(char c)

     {

         if (Character.isDigit(c))return c-'0';

         if (Character.isUpperCase(c))return c-'A'+10;

         if (Character.isLowerCase(c))return c-'a'+36;

         return '0';

     }

     public static char GetChar(int x)

     {

         if (x<10)return (char)(x+'0');

         else if (x<=35) return (char)(x+'A'-10);

         else return (char)(x+'a'-36);

     }

     public static void main(String[] args)

     {

         Scanner cin= new Scanner(new BufferedInputStream(System.in));

         int T=cin.nextInt();

         while(T--!=0)

         {

             BigInteger base1=cin.nextBigInteger();

             BigInteger base2=cin.nextBigInteger();

             BigInteger n=BigInteger.ZERO;

             String s=cin.next();

             for(int i=0;i<s.length();i++)

             {

                 char c=s.charAt(i);

                 n=n.multiply(base1).add(BigInteger.valueOf(GetNum(c)));

             }

             String ans=new String();

             while(!n.equals(BigInteger.ZERO))

             {

                 ans=GetChar(n.mod(base2).intValue())+ans;

                 n=n.divide(base2);

             }

             if(ans.length()==0) ans+='0';

             System.out.println(base1+" "+s);

             System.out.println(base2+" "+ans);

             if (T>0)System.out.println();

         }

     }

 }

 import java.io.*;

 import java.math.*;

 import java.util.*;

 public class Main {

     public static void main(String[] args)

     {

         Scanner cin=new Scanner(new BufferedInputStream(System.in));

         BigDecimal b= new BigDecimal("8"),k,ans;

         String s;

         while(cin.hasNext())

         {

             ans=new BigDecimal(0);

             k=new BigDecimal(1);

             s=cin.nextLine();

             for(int i=2;i<s.length();i++)

             {

                 k=k.divide(b);

                 ans=ans.add( BigDecimal.valueOf(s.charAt(i)-'0').multiply(k));

             }

             System.out.println(s+" [8] = "+ans.toString()+" [10]");

             //System.out.println(s+" [8] = "+ans.toString()+" [10]");

         }

     }

 }

 import java.io.*;

 import java.math.*;

 import java.util.*;

 public class Main {

     public static void main(String[] args)

     {

         Scanner cin=new Scanner(new BufferedInputStream(System.in));

         BigInteger f[]=new BigInteger[1005],Three=BigInteger.valueOf(3);

         BigInteger tp[][]=new BigInteger[3][3],a[][]=new BigInteger[3][3];

         a[1][1]=Three; a[1][2]=BigInteger.valueOf(-1);

         a[2][1]=BigInteger.ONE; a[2][2]=BigInteger.ZERO;

         f[0]=BigInteger.ZERO;

         f[1]=BigInteger.ONE;

         for(int i=2;i<=1000;i++)

             f[i]=f[i-1].multiply(Three).subtract(f[i-2]);

         while(cin.hasNext())

         {

             int n=cin.nextInt();

             tp=MatrixPower(a,2,n-1);

             System.out.println(tp[1][1].toString());

         }

     }

     public static BigInteger[][] MatrixMultiply(BigInteger a[][],BigInteger b[][],int n,int p,int m)

     {

         BigInteger c[][]=new BigInteger[n+1][m+1];

         for(int i=1;i<=n;i++)

         for(int j=1;j<=m;j++)

             c[i][j]=BigInteger.ZERO;

         for(int i=1;i<=n;i++)

         for(int j=1;j<=m;j++)

         for(int k=1;k<=p;k++)

             c[i][j]=c[i][j].add(a[i][k].multiply(b[k][j]));

         return c;

     }

     public static BigInteger[][] MatrixPower(BigInteger a[][],int n,int p)

     {

         BigInteger ans[][]=new BigInteger[n+1][n+1];

         for(int i=1;i<=n;i++)

         for(int j=1;j<=n;j++)

             if (i==j)ans[i][j]=BigInteger.ONE;

             else ans[i][j]=BigInteger.ZERO;

         while(p>0)

         {

             if ((p&1)==1)ans=MatrixMultiply(ans,a,n,n,n);

             p=p/2;

             a=MatrixMultiply(a,a,n,n,n);

         }

         return ans;

     }

 }