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--;

		}

	}

}