Background

During the “Gekokujou Incident”, Hakurei Reimu fought her way up to Tenshukaku to find the source of the incident.

The mastermind, Kijin Seija, kept flipping Tenshukaku over and over to fight back, and the old, poorly maintained Tenshukaku ended up losing many floor tiles.

After the incident, Sukuna returned to Tenshukaku at her normal size. She wants to repair the floor, but she needs to know how many tiles she must buy (a shocking number). So she asks you, an expert in $\text{OI}$, for help.

Problem Description

To make the Miracle Mallet unleash its full power, Sukuna will use the tiles she buys to completely cover a square of any side length (because the tiles have patterns, rotation is not allowed, and of course tiles are not allowed to overlap) to achieve maximum resonance.

In each purchase, Sukuna can only buy tiles of one fixed size $a*b$. To save money, under the condition that they can form a square, she will buy as few tiles as possible.

Now, for every pair $a,b(1 \le a,b \le n)$, she wants to know the minimum number of tiles needed. Of course, since the output may be very large, you only need to output the product of all answers modulo 19260817.

Input Format

The first line contains an integer $\text{T}$, the number of test cases.

The next $\text{T}$ lines each contain one integer $n$.

Output Format

Output $\text{T}$ lines in total, each containing one integer, the answer modulo 19260817.

4
1
2
3
100

1
4
1296
18996121

Hint

Sample Explanation

For n=1, there is only one pair $(a,b)$, namely $(1,1)$. Only one $1*1$ tile is needed to form a square of side length 1, so the answer is $1$.

For n=2, the pairs $(a,b)$ are $(1,1),(1,2),(2,1),(2,2)$. They need $1,2,2,1$ tiles respectively to form a square, so the answer is $1*2*2*1=4$.

Further explanation:

When only $1*1$ tiles are available, only one tile is needed (it is already a square).

When only $1*2$ tiles are available, two tiles are needed (two tiles put together form a $2*2$ square).

Constraints

For $30\%$ of the testdata, $1 \le T \le 100, 1 \le n \le 100$.

For $60\%$ of the testdata, $1 \le T \le 300, 1 \le n \le 3*10^4$.

For $100\%$ of the testdata, $1 \le T \le 1000, 1 \le n \le 10^6$.

Translated by ChatGPT 5