FBI 범용 관리 번호

FBI는 지문 데이터베이스에 등록된 사람을 식별하는 범용 관리 번호(UCN)를 27진법 여덟 자리에 검사 숫자 한 자리를 덧붙인 아홉 자리 값으로 바꿨다. 자릿값으로 쓰는 글자는 다음 27개다.

0123456789ACDEFHJKLMNPRTVWX

나머지 알파벳은 다른 자릿값과 혼동되기 쉬워 쓰지 않는다. 입력에 이 글자가 나오면 아래 대응표대로 바꾼다.

B->8, G->C, I->1, O->0, Q->0, S->5, U->V, Y->V, Z->2

검사 숫자는 다음 식으로 구한다.

$(2 D_1 + 4 D_2 + 5 D_3 + 7 D_4 + 8 D_5 + 10 D_6 + 11 D_7 + 13 D_8) \bmod 27$

여기서 $D_n$은 왼쪽에서 $n$번째 자릿값이다. 이렇게 정한 검사 숫자는 자릿값 하나가 틀린 경우와 앞 여덟 자리 중 이웃한 두 자리가 뒤바뀐 경우를 모두 잡아낸다.

사용자가 입력한 UCN을 해석하는 프로그램을 작성하라. 십진 숫자와 대문자 알파벳은 모두 자릿값으로 받아들인다. 혼동되는 글자는 아홉 번째 글자까지 포함해 위 표대로 바꾼 다음, 올바른 검사 숫자를 계산해 입력된 검사 숫자와 비교한다. 두 값이 다르면 입력을 거부하고, 같으면 앞 여덟 자리가 나타내는 27진법 수의 십진수 값을 출력한다.

첫째 줄에 데이터 집합의 개수 $P$가 주어진다. ($1 \le P \le 10000$)

다음 $P$개 줄에 데이터 집합이 한 줄에 하나씩 주어진다. 각 줄은 데이터 집합 번호 $K$, 공백 한 개, 십진 숫자나 대문자 알파벳 아홉 글자로 이루어진다.

데이터 집합은 서로 독립이며 모두 같은 방식으로 처리한다.

데이터 집합마다 한 줄씩 출력한다. 데이터 집합 번호 $K$, 공백 한 개에 이어 검사 숫자가 맞지 않으면 Invalid를, 맞으면 앞 여덟 자리가 나타내는 십진수 값을 출력한다.