성실한 암호 담당자

할보르는 Identity Directories, Inc.의 통합 인증(SSO) 로그인 시스템을 담당한다. 그는 몇 년째 이 기술을 열렬히 지지해 왔고, Trustworthy Enterprises(TE)가 제공하는 암호화 로그인 백엔드 덕분에 사용자 인증이 더 간단하고 안전해진다고 주변에 이야기하고 다녔다. 지난주 할보르는 TE의 소식지를 받았다. 소식지에는 새로 만든 Open Trust Protection(OTP) 시스템 소개가 실려 있었다. OTP는 최근에 도입되었고, 신규 계정과 지난달에 비밀번호를 바꾼 사용자에게 이미 쓰이고 있다.

예전 시스템에서 사용자의 암호 키는 알파벳 앞쪽 몇 글자를 한 번씩만 쓴 순열을, 긴 메시지에도 쓸 수 있도록 여러 번 이어 붙인 문자열이었다. 새 시스템에서는 라바 램프를 쓰는 하청 업체가 만든 무작위 글자가 그대로 키가 된다.

예를 들어 BCAEDBCAEDBCAED는 예전 시스템에서 나올 수 있는 키다. A부터 E까지의 순열인 BCAED를 반복한 문자열이기 때문이다. 반면 BCDBCD와 BABBABBABBAB는 나올 수 없다. 반복되는 BCD에는 A가 없고, BAB은 B가 두 개라서 AB의 순열이 아니다.

할보르는 아직 새 시스템으로 자동 이전되지 않은 사용자의 키를 직접 바꾸려고 한다. 그는 담당 사용자의 키를 모두 읽고 쓸 수 있어서, 어떤 사용자를 갱신해야 하는지 판별하는 프로그램을 여러분에게 의뢰했다. 개인정보 문제를 피하려고 여러분이 받는 정보는 사용자 이름, 마지막 로그인 시각, 키의 앞부분 1000글자까지가 전부다.

그래서 예전 시스템의 키라면 받은 문자열의 끝이 순열 중간에서 잘려 있을 수 있다. 다만 첫 글자는 순열의 시작이라고 보장한다. 새 시스템의 키라면 받은 부분을 포함해 문자열 전체가 무작위다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 사용자 암호 키의 앞부분인 문자열 $K$ 한 줄로 이루어진다.

• $1 \le T \le 1000$
• $1 \le |K| \le 1000$
• 입력 문자열의 글자는 모두 대문자다 (보충 설명)
• 엔트로피는 $H(X) = -\sum_{i=1}^{n} p(x_i) \log_b(x_i)$로 쓸 수 있다. 여기서 $p$는 $X$의 확률 질량 함수다.

각 테스트 케이스마다 한 줄을 출력한다. $K$가 예전 시스템에서 왔다고 확신할 수 있으면 old, 새 시스템에서 왔다고 확신할 수 있으면 new, 주어진 키 앞부분만으로는 판별할 수 없으면 unknown을 출력한다.