Background

Zszz, the main character always writes a little essay in their mind while taking the elevator down before the class trial.

But what if they cannot write anything? Zzz ......

So Saihara started thinking about math problems ......

Problem Description

There are positive integers $a, b, c$ satisfying the $\alpha$ equation: $\dfrac{1}{a} - \dfrac{1}{b} = \dfrac{1}{c}$, and $\gcd(a, b, c) = 1$.

Given a positive integer $N$, write a program to compute the number of $\alpha$ equations with $c \leq N$, and output one $b$ that satisfies the following condition:

Among all $\alpha$ equations with $c = N$, choose one with the smallest $a$.

Input Format

The first line contains a positive integer $T$, the number of queries.

The next $T$ lines each contain one positive integer, the given $N$.

Output Format

Output $T$ lines. Each line contains a positive integer, the number of $\alpha$ equations that satisfy the condition. If a solution exists, output a space and then output one valid $b$.

It can be proven that when $N > 1$, such a $b$ always exists.

2
1
2

0
1 2

2
233
2020

479 54056
5470 8181

Hint

Sample #2 Explanation

In the first query, the corresponding equation is: $\dfrac{1}{232} - \dfrac{1}{54056} = \dfrac{1}{233}$, so the second output is $54056$.

In the second query, the corresponding equation is: $\dfrac{1}{1620} - \dfrac{1}{8181} = \dfrac{1}{2020}$, so the second output is $8181$.

And in these two $\alpha$ equations, $a$ is the smallest among all cases with $c = N$.

Constraints

For $10\%$ of the testdata, $N \leq 100$, $T \leq 10$.

For $30\%$ of the testdata, $N \leq 10^3$, $T \leq 100$.

For $70\%$ of the testdata, $N \leq 10^5$, $T \leq 10^4$.

For $100\%$ of the testdata, $N \leq 2 \times 10^6$, $T \leq 10^5$.

About Special Judge

This problem uses Special Judge.

If you answer the first question all correctly but make mistakes on the second question, you will get $30\%$ of the score. If you answer the first question incorrectly but answer the second question all correctly, you will get $70\%$ of the score. However, if both the first and the second questions have some or all wrong answers, you will be judged as WA. Also, if your output is incomplete or has extra parts, for example, you only answer the first question but do not output the answer for the second question (except when $N = 1$), or you output one extra number when $N = 1$, then you will also get no score.

Translated by ChatGPT 5