Description

你正在尝试计算由一个秘密代码生成的数列 $S_n$ 的下一个数字。你已知该代码是按照以下过程生成的。

首先，对于每个 $k$ 从 $0$ 到 $29$，选择一个介于 $0$ 到 $10006$（包含）之间的数字 $C_k$。

然后，对于每个 $n$ 从 $0$ 到 $1\ 000\ 000\ 000$（包含）：

• 将 $n$ 写成二进制形式。
• 对于 $n$ 的二进制表示中每一个被置位的比特 $k$，取出对应的 $C_k$。例如，当 $n=5$ 时，二进制下第 $0$ 位和第 $2$ 位被置位，因此取 $C_0$ 和 $C_2$。
• 将这些 $C_k$ 相加，除以 $10007$，输出余数作为 $S_n$。

你将获得数列 $S$ 的一段连续值，但你不知道这些数字在数列中的起始位置（不过你知道数列中至少还有下一个数字），也不知道生成数列时选取的 $C_k$ 的具体值。

请你找出该数列的下一个数字，或者如果无法确定，则输出 UNKNOWN。

Input Format

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例，包含：

• 一行一个整数 $N$，表示你已知的数列 $S$ 的元素个数。
• 一行包含 $N$ 个用单个空格分隔的整数，范围在 $0$ 到 $10006$ 之间，表示已知的数列元素。

Output Format

对于每个测试用例，输出一行，格式为 “Case #$X$: $Y$”，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是该数列的下一个数字，或者如果无法确定则输出字符串 UNKNOWN。

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

Hint

样例解释

在第一个样例中，$C_0$、$C_1$ 和 $C_2$ 可能分别为 $1$、$2$ 和 $4$，我们已知的 $S_n$ 是从 $n=1$ 开始的。如果是这样，我们并不知道 $C_3$ 的值，因此下一个数列值可能是任意值！所以答案是 UNKNOWN。

在第二个样例中，我们无法知道所有 $C_k$ 的值，甚至不知道 $n$ 是多少，但我们可以证明，在任何数列中，如果 $1$、$10$、$11$、$200$ 按顺序出现，那么下一个值一定是 $201$。

数据范围

• $1 \leqslant T \leqslant 20$

小数据范围（7 分，测试点 1 - 可见）

• $1 \leqslant N \leqslant 5$

大数据范围（15 分，测试点 2 - 隐藏）

• $1 \leqslant N \leqslant 1000$

由 ChatGPT 4.1 翻译