天守阁的地板

题目背景

在下克上异变中,博丽灵梦为了找到异变的源头,一路打到了天守阁。 异变主谋鬼人正邪为了迎击,将天守阁反复颠倒过来,而年久失修的天守阁也因此掉下了很多块地板。 异变结束后,恢复了正常大小的小碗回到了天守阁,想要修复这里的地板,她需要知道自己要采购的地板数量(一个惊人的数字),于是,她找到了精通 $\text{OI}$ 的你来帮忙。

题目描述

为了使万宝槌能发挥出全部魔力,小碗会将买来的地板铺满一个**任意**边长的正方形(地板有图案,因此**不允许旋转**,当然,地板也**不允许重叠**)来达到最大共鸣。 在每一次购买中,小碗只能买到一种规格为 $a*b$ 的地板,为了省钱,她会在满足能摆成正方形的前提下购买尽可能少的地板。 现在,她想知道对于每一对 $a,b(1≤a,b≤n)$ ,她最少需要购买的地板数量。当然,由于输出可能很大,你只需要输出所有答案的乘积对 `19260817` 取模后的结果即可。

输入输出格式

输入格式


第一行一个整数 $\text{T}$ ,表示数据组数 下面 $\text{T}$ 行,每行一个整数 $n$

输出格式


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

输入输出样例

输入样例 #1

4
1
2
3
100

输出样例 #1

1
4
1296
18996121

说明

#### 样例解释: 对于`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$