Code Sequence (Large)

A sequence $S$ is generated from a secret code, and you have to work out its next term. The code was built as follows.

First, for each $k$ from $0$ to $29$, a number $C_k$ between $0$ and $10006$ inclusive was chosen.

Then, for every integer $n$ from $0$ to $10^9$ inclusive:

• Write $n$ in binary.
• Collect $C_k$ for every bit $k$ that is set in that binary representation. For $n = 5$, bits 0 and 2 are set, so $C_0$ and $C_2$ are collected.
• Add the collected values, divide by $10007$, and let the remainder be $S_n$.

You are given several consecutive terms of $S$. You do not know where in the sequence they start, though you do know that at least one more term follows them, and you do not know which $C_k$ were chosen.

Print the term that comes right after the given ones. If the input does not pin it down to a single value, print UNKNOWN.

The first line contains the number of test cases $T$.

Each test case takes two lines.

• The first line contains $N$, the number of known terms.
• The second line contains the $N$ known terms, separated by single spaces. Each term is between $0$ and $10006$.

Limits

• $1 \le T \le 20$
• $1 \le N \le 1000$
• Every test case is a consecutive block of some sequence the procedure above can produce, and at least one more term follows the last given one. That is, there are $C_0, \dots, C_{29}$ and an index $m$ with $0 \le m \le 10^9 - N$ such that the given terms are $S_m, S_{m+1}, \dots, S_{m+N-1}$ in this order.

For each test case print one line in the form Case #$X$: $Y$, where $X$ is the test case number starting from 1 and $Y$ is the next term. Write UNKNOWN in place of $Y$ when the next term is not determined.

In the first test case of the sample input, $C_0, C_1, C_2$ could have been 1, 2 and 4, with the given terms starting at $n = 1$. Read that way, $C_3$ is unknown, so the next term could be anything and the answer is UNKNOWN.

In the second test case neither the full list of $C_k$ nor the starting index can be recovered. Even so, whenever 1, 10, 11, 200 occur consecutively in this order, the next value is always 201.