1 import java.util.Scanner;
 2 
 3 public class Main {
 4     public static void main(String[] args) {
 5         Scanner in = new Scanner(System.in);
 6         int count = in.nextInt();
 7         int[] aa = new int[count];
 8         for(int i=0;i<count;i++)
 9         {
10             int a = in.nextInt();
11             String temp = in.next();
12             int b = in.nextInt();
13             
14             int len = temp.length()+1;
15             if(a<b)
16             {
17                 int c = a;
18                 a = b; 
19                 b = c;
20             }
21             String tep = func(a,b,len);
22             aa[i]=output(tep,len);
23         }
24         for(int i=0;i<count;i++)
25         {
26             System.out.println(aa[i]);            
27         }
28     }
29     //转换成n+1进制
30     public static String change(int a,int len,String result)
31     {
32         result = (a%len)+result;
33         if(a/len>0)return change(a/len,len,result);
34         return result;
35     }
36    //进行计算
37     public static String func(int a,int b,int len)
38     {
39         String ta = change(a,len,"");
40         String tb = change(b,len,"");
41         int max = ta.length();
42         int min = tb.length();
43           for(int k=min; k<max;k++)
44           {
45               tb = "0"+tb;
46           }
47         String result ="";
48 
49         for(int i=0;i<max;i++)
50         {
51             int asd = (Integer.parseInt(tb.substring(i,i+1))+ Integer.parseInt(ta.substring(i,i+1)))%len;
52             result += String.valueOf(asd);          
53         }
54         return result;
55     }
56     //转换回10进制
57     public static int output(String result,int len)
58     {
59         int ok = 0;
60         int bei = 1;
61         for(int i = result.length()-1;i>=0;i--)
62         {
63             int cu = Integer.parseInt(result.substring(i,i+1));
64             ok += cu*bei;
65             bei*=len;
66         }
67         return ok;
68     }
69 }