题目描述

You are trying to compute the next number in a sequence $S_n$ generated by a secret code. You know that the code was generated according to the following procedure.

First, for each $k$ between $0$ and $29$, choose a number $C_k$ between $0$ and $10006$ (inclusive).

Then, for each integer $n$ between $0$ and $1\ 000\ 000\ 000$ (inclusive):

• Write $n$ in binary.
• Take the numbers $C_k$ for every bit $k$ that is set in the binary representation of $n$. For example, when $n=5$, bits $0$ and $2$ are set, so $C_0$ and $C_2$ are taken.
• Add these $C_k$ together, divide by $10007$, and output the remainder as $S_n$.

You will be given a series of consecutive values of sequence $S$, but you don't know at which point in the sequence your numbers begin (although you do know that there is at least one more number in the sequence), and you don't know what values of $C_k$ were chosen when the sequence was generated.

Find the next number in the sequence, or output UNKNOWN if this cannot be determined from the input data.

输入格式

The first line will contain an integer $T$, the number of test cases in the input file.

For each test case, there will be:

• One line containing the integer $N$, the number of elements of sequence $S$ that you have.
• One line containing $N$ single-space-separated integers between $0$ and $10006$, the known elements of the sequence.

输出格式

For each test case, output one line containing "Case #$X$: $Y$" where $X$ is the number of the test case, starting from $1$, and $Y$ is the next number in the sequence, or the string UNKNOWN if the next number cannot be determined.

3
7
1 2 3 4 5 6 7
4
1 10 11 200
4
1000 1520 7520 7521

Case #1: UNKNOWN
Case #2: 201
Case #3: 3514

提示

Sample Explanation

In the first case, $C_0$, $C_1$ and $C_2$ might have been $1$, $2$ and $4$, and the values of $S_n$ we have starting at $n=1$. If this is correct, we don't know $C_3$, so the next number in the sequence could be anything! Therefore the answer is unknown.

In the second case, we cannot know all the values of $C_k$ or even what $n$ is, but we can prove that in any sequence, if $1$, $10$, $11$, $200$ occur in order, then the next value will always be $201$.

Limits

• $1 \leqslant T \leqslant 20$

Small dataset (7 Pts, Test set 1 - Visible)

• $1 \leqslant N \leqslant 5$

Large dataset (15 Pts, Test set 2 - Hidden)

• $1 \leqslant N \leqslant 1000$