Description

为了使万宝槌能发挥出全部魔力，小碗会将买来的地板铺满一个任意边长的正方形(地板有图案，因此不允许旋转，当然，地板也不允许重叠)来达到最大共鸣。

在每一次购买中，小碗只能买到一种规格为 $a*b$ 的地板，为了省钱，她会在满足能摆成正方形的前提下购买尽可能少的地板。

现在，她想知道对于每一对 $a,b(1≤a,b≤n)$ ，她最少需要购买的地板数量。当然，由于输出可能很大，你只需要输出所有答案的乘积对 19260817 取模后的结果即可。

Input Format

第一行一个整数 $\text{T}$ ，表示数据组数

下面 $\text{T}$ 行，每行一个整数 $n$

Output Format

共 $\text{T}$ 行，每行一个整数，表示取模后的答案

4
1
2
3
100

1
4
1296
18996121

Hint

样例解释:

对于n=1，$(a,b)$ 仅有 $(1,1)$ 一种情况，只需要一块 $1 * 1$ 的地板即可构成边长为1的正方形,答案为 $1$

对于n=2，$(a,b)$ 有 $(1,1),(1,2),(2,1),(2,2)$ 四种情况，分别需要 $1,2,2,1$ 块地板以拼成正方形，答案为 $1*2*2*1=4$

进一步解释：

当只能买到 $1*1$ 的地板时，只需要一块(本身就是正方形)

当只能买到 $1*2$ 的地板时，需要两块(两块拼在一起组成 $2*2$ 的正方形)

数据范围：

对于 $30\%$ 的数据，$1 \le T \le 100,1 \le n \le 100$

对于 $60\%$ 的数据，$1 \le T \le 300,1 \le n \le 3*10^4$

对于 $100\%$ 的数据，$1 \le T \le 1000,1 \le n \le 10^6$