#include <iostream>
#include <math.h>
using namespace std;
// convert number r-based to 10-based
int convertAnyToDecimal(string number, int based) {
int result = 0, exponent = 0;
for (int i = number.length() - 1; i >= 0 ; i--) {
int numberParsed =
('0' <= number[i] && number[i] <= '9')
? number[i] - '0'
: number[i] - 55;
result += numberParsed * pow(based, exponent++);
}
return result;
}
// convert number 10-based to s-based
string convertDecToAny(int numInDecimal, int basedTo) {
string result = "";
while (numInDecimal != 0) {
result = to_string(numInDecimal % basedTo) + result;
numInDecimal /= basedTo;
}
return result;
}
// convert number r-based to s-based
string convertNumber(string number, int based, int basedTo) {
// convert number r-based to 10-based
int numInDecimal;
if (based != 10)
numInDecimal = convertAnyToDecimal(number, based);
else
numInDecimal = stoi(number);
// convert number 10-based to s-based
string result = "";
if (basedTo != 10)
result = convertDecToAny(numInDecimal, basedTo);
else
result = to_string(numInDecimal);
return result;
}
int main() {
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
string n; // <= 10^1000
int r, s; // <= 36
cin >> n;
cin >> r >> s;
string result = convertNumber(n, r, s);
cout << result << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWF0aC5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCi8vIGNvbnZlcnQgbnVtYmVyIHItYmFzZWQgdG8gMTAtYmFzZWQKaW50IGNvbnZlcnRBbnlUb0RlY2ltYWwoc3RyaW5nIG51bWJlciwgaW50IGJhc2VkKSB7CglpbnQgcmVzdWx0ID0gMCwgZXhwb25lbnQgPSAwOwoJCglmb3IgKGludCBpID0gbnVtYmVyLmxlbmd0aCgpIC0gMTsgaSA+PSAwIDsgaS0tKSB7CgkJaW50IG51bWJlclBhcnNlZCA9CgkJCQkoJzAnIDw9IG51bWJlcltpXSAmJiBudW1iZXJbaV0gPD0gJzknKSAKCQkJCT8gbnVtYmVyW2ldIC0gJzAnIAoJCQkJOiBudW1iZXJbaV0gLSA1NTsKCQlyZXN1bHQgKz0gbnVtYmVyUGFyc2VkICogcG93KGJhc2VkLCBleHBvbmVudCsrKTsKCX0KCQoJcmV0dXJuIHJlc3VsdDsKfQogCi8vIGNvbnZlcnQgbnVtYmVyIDEwLWJhc2VkIHRvIHMtYmFzZWQKc3RyaW5nIGNvbnZlcnREZWNUb0FueShpbnQgbnVtSW5EZWNpbWFsLCBpbnQgYmFzZWRUbykgewoJc3RyaW5nIHJlc3VsdCA9ICIiOwoJd2hpbGUgKG51bUluRGVjaW1hbCAhPSAwKSB7CgkJcmVzdWx0ID0gdG9fc3RyaW5nKG51bUluRGVjaW1hbCAlIGJhc2VkVG8pICsgcmVzdWx0OwoJCW51bUluRGVjaW1hbCAvPSBiYXNlZFRvOwoJfQoJcmV0dXJuIHJlc3VsdDsKfQogCi8vIGNvbnZlcnQgbnVtYmVyIHItYmFzZWQgdG8gcy1iYXNlZApzdHJpbmcgY29udmVydE51bWJlcihzdHJpbmcgbnVtYmVyLCBpbnQgYmFzZWQsIGludCBiYXNlZFRvKSB7CgkvLyBjb252ZXJ0IG51bWJlciByLWJhc2VkIHRvIDEwLWJhc2VkCglpbnQgbnVtSW5EZWNpbWFsOwoJaWYgKGJhc2VkICE9IDEwKQoJCW51bUluRGVjaW1hbCA9IGNvbnZlcnRBbnlUb0RlY2ltYWwobnVtYmVyLCBiYXNlZCk7CgllbHNlCgkJbnVtSW5EZWNpbWFsID0gc3RvaShudW1iZXIpOwoJCgkvLyBjb252ZXJ0IG51bWJlciAxMC1iYXNlZCB0byBzLWJhc2VkCglzdHJpbmcgcmVzdWx0ID0gIiI7CglpZiAoYmFzZWRUbyAhPSAxMCkKCQlyZXN1bHQgPSBjb252ZXJ0RGVjVG9BbnkobnVtSW5EZWNpbWFsLCBiYXNlZFRvKTsKCWVsc2UKCQlyZXN1bHQgPSB0b19zdHJpbmcobnVtSW5EZWNpbWFsKTsKCQoJcmV0dXJuIHJlc3VsdDsKfQogCmludCBtYWluKCkgewoJaW50IE47CgljaW4gPj4gTjsKCWZvciAoaW50IGkgPSAxOyBpIDw9IE47IGkrKykgewoJCXN0cmluZyBuOyAvLyA8PSAxMF4xMDAwCgkJaW50IHIsIHM7IC8vIDw9IDM2CgkJY2luID4+IG47CgkJY2luID4+IHIgPj4gczsKCQlzdHJpbmcgcmVzdWx0ID0gY29udmVydE51bWJlcihuLCByLCBzKTsKCQljb3V0IDw8IHJlc3VsdCA8PCBlbmRsOwoJfQoJcmV0dXJuIDA7Cn0gIA==