코드 수열

당신은 비밀 코드로 생성된 수열 $S_{n}$에서 다음 수를 계산하려고 한다. 이 코드는 다음 절차에 따라 생성되었다는 것을 알고 있다.

먼저, 0에서 29 사이의 각 k에 대해, 0에서 10006 사이(양 끝 포함)의 수 $C_{k}$를 하나 선택한다.

그런 다음, 0에서 1000000000 사이(양 끝 포함)의 각 정수 n에 대해 다음을 수행한다.

• n을 이진수로 쓴다.

• n의 이진 표현에서 설정된 모든 비트 k에 대해 수 $C_{k}$를 취한다. 예를 들어 n=5일 때 비트 0와 2가 설정되어 있으므로, $C_{0}$와 $C_{2}$를 취한다.

• 이 $C_{k}$를 모두 더하고, 10007로 나눈 뒤, 나머지를 $S_{n}$로 출력한다.

수열 S에서 연속한 값들이 주어지지만, 그 값들이 수열의 어느 지점에서 시작하는지는 알 수 없다(단, 수열에 적어도 하나의 수가 더 남아 있다는 것은 알고 있다). 또한 수열이 생성될 때 $C_{k}$에 어떤 값들이 선택되었는지도 알 수 없다.

수열의 다음 수를 구하거나, 입력 데이터만으로 이를 결정할 수 없다면 UNKNOWN을 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 20

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 5

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000

첫째 줄에는 입력 파일의 테스트 케이스 수를 나타내는 정수 T가 주어진다.

각 테스트 케이스에는 다음이 주어진다.

• 보유한 수열 S의 원소 수를 나타내는 정수 N이 한 줄에 주어진다.

• 수열에서 알고 있는 원소인, 0에서 10006 사이의 정수 N개가 공백 하나로 구분되어 한 줄에 주어진다.

각 테스트 케이스마다 "Case #X: Y"을 한 줄에 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 수열의 다음 수이다. 다음 수를 결정할 수 없다면 문자열 UNKNOWN을 출력한다.

첫 번째 경우에는 $C_{0}$, $C_{1}$, $C_{2}$이 각각 1, 2, 4였을 수도 있으며, 우리가 가진 $S_{n}$의 값들은 n=1부터 시작했을 수도 있다. 이것이 맞다면 $C_{3}$을 알 수 없으므로, 수열의 다음 수는 무엇이든 될 수 있다! 따라서 답은 알 수 없다.

두 번째 경우에는 $C_{k}$의 값을 모두 알 수도 없고 n이 무엇인지조차 알 수 없지만, 어떤 수열에서든 1, 10, 11, 200가 순서대로 나타나면 다음 값은 항상 201이 된다는 것을 증명할 수 있다.