package com.njupt.acm;
import java.math.BigInteger;
import java.util.Scanner;
public class POJ_1220_1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t > 0){
BigInteger ba1 = scanner.nextBigInteger();
BigInteger ba2 = scanner.nextBigInteger();
BigInteger sum = new BigInteger("0");
String str = scanner.next();
int len = str.length();
int i;
int count = 0;
int temp;
for(i = len - 1; i >= 0 ; --i){//先将输入的ba1进制的数按照给定的规则转化成10进制的数
char w = str.charAt(i);
temp = 0;
if(Character.isDigit(w)){
temp = w - '0';
}else if(Character.isLowerCase(w)){
temp = w - 'a' + 36;
}else if(Character.isUpperCase(w)){
temp = w - 'A' + 10;
}
sum = sum.add(new BigInteger(temp + "").multiply(ba1.pow(count++)));
}
BigInteger zero = new BigInteger("0");
int top = 0;
int stack[] = new int[2000];
while(sum.compareTo(zero) != 0){//转化成指定ba2进制的数
stack[++top] = sum.mod(ba2).intValue();
sum = sum.divide(ba2);
}
System.out.println(ba1+" "+str);
System.out.print(ba2+" ");
if(top == 0){
System.out.print(0);
}
while(top != 0){
char w = 0;
temp = stack[top--];
if(temp < 10){
w = (char) (temp +'0');
}else if(temp>= 10 && temp < 36){
w = (char) (temp +'A' - 10);
}else if(temp >= 36){
w = (char) (temp + 'a' - 36);
}
System.out.print(w);
}
System.out.println();
System.out.println();
t--;
}
}
}
