#include <iostream>#include <cstring>#include <stdio.h>using namespace std;int char2int(char bit){if(bit >= '0' && bit <= '9')return (int)(bit - '0');else if(bit >= 'A' && bit <= 'Z')return (int)(bit - 'A') + 10;elsereturn (int)(bit - 'a') + 36;}char int2char(int bit){if(bit >= 0 && bit <= 9)return (char)(bit + '0');else if(bit >= 10 && bit <= 35)return (char)(bit - 10 + 'A');elsereturn (char)(bit - 36 + 'a');}int main(){int T,i,cnt,length,base_in,base_out,quotient,remainder;int oct[1000];char input[1000];char output[1000];scanf("%d",&T);while(T--){scanf("%d%d%s",&base_in,&base_out,&input);length = strlen(input);if(length == 1 && input[0] == '0'){printf("%d 0n%d 0nn",base_in,base_out);continue;}for(i = 0;i < length;i ++)oct[i] = char2int(input[i]);oct[length] = -1;cnt = 0;while(1){i = 0;while(oct[i] == 0)i++;if(i == length)break;remainder = 0;while(oct[i] != -1){quotient = (oct[i] + remainder * base_in) / base_out;remainder = (oct[i] + remainder * base_in) % base_out;oct[i++] = quotient;}output[cnt++] = int2char(remainder);}printf("%d %sn",base_in,input);printf("%d ",base_out);for(i = cnt - 1;i >= 0;i --)printf("%c",output[i]);printf("nn");}return 0;}
