for _ in'.'*int(input()):
 u=int(s:=input(),16)*int('3LK2RCDXXAE3I64MB8PU56MC5',36);s+=':'
 while u:s+=chr(u%128);u>>=7
 print(s)