从前，有一位 NWERC 的裁判，他总是倾向于出一些稍微有点太难的题目。结果，他的题目从来没有人能做出来。正如你能想象的那样，这让我们的裁判感到有些沮丧。今年，这种沮丧达到了顶点，他决定不再花大量时间去构思一道精心设计的题目，而是直接写一个极其困难的题面，然后随机生成一些输入和输出文件。毕竟，既然反正没人会去尝试这道题，又何必费尽心思去制作正规的测试数据呢？

因此，裁判生成测试用例的方法非常简单：直接让输入是一个随机数，输出是另一个随机数。具体来说，为了生成包含 $T$ 个测试用例的数据集，裁判生成了 $2T$ 个介于 $0$ 到 $10\,000$ 之间的随机数 $x_1, \dots, x_{2T}$，然后将 $T$ 以及序列 $x_1, x_3, x_5, \dots, x_{2T-1}$ 写入输入文件，将序列 $x_2, x_4, x_6, \dots, x_{2T}$ 写入输出文件。

裁判使用的随机数生成器非常简单。他选择三个介于 $0$ 到 $10\,000$（含）之间的数字 $x_1$、$a$ 和 $b$，然后对于 $i$ 从 $2$ 到 $2T$，令：

$$x_i = (a \cdot x_{i-1} + b) \bmod 10\,001$$

你可能会认为，这样设计粗劣的题目是不会出现在像 NWERC 这样高水平的比赛中的。好吧，你错了。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 $100$。接下来每个测试用例：

• 包含一个整数 $n$ ($0 \le n \le 10\,000$) 的一行：一个输入测试用例。

保证输入文件是通过上述过程生成的。

输出格式

对于每个测试用例：

• 输出一行，包含一个整数，表示该测试用例的答案。

如果存在多个与输入文件一致的输出，任何一个都是可以接受的。

样例

输入样例 1

3
17
822
3014

输出样例 1

9727
1918
4110