m = {
"0": 0,
"1": 1,
"2": 2,
"3": 3,
"4": 4,
"5": 5,
"6": 6,
"7": 7,
"8": 8,
"9": 9,
"A": 10,
"B": 8,
"C": 11,
"D": 12,
"E": 13,
"F": 14,
"G": 11,
"H": 15,
"I": 1,
"J": 16,
"K": 17,
"L": 18,
"M": 19,
"N": 20,
"O": 0,
"P": 21,
"Q": 0,
"R": 22,
"S": 5,
"T": 23,
"U": 24,
"V": 24,
"W": 25,
"X": 26,
"Y": 24,
"Z": 2,
}
w = [2, 4, 5, 7, 8, 10, 11, 13]
for _ in range(int(input())):
i, d = input().split()
t = sum([m[b] * a for a, b in zip(w, d)])
if t % 27 == m[d[-1]]:
s = sum([m[b] * 27**a for a, b in zip(range(8), d[:8][::-1])])
print(f"{i} {s}")
else:
print(f"{i} Invalid")