Easy Pythagorean Triplet

One day Mostafiz and Evan were talking about Pythagoras. Mostafiz told that Pythagorean Triplet is very much interesting. Hearing that, Evan told that he knew everything about Pythagorean Triplet. But, Actually, Evan doesn’t know anything about it.

Then, Mostafiz gives an easy problem to solve. But, Evan can’t solve it. Can you solve the problem?

The problem was:

All we know about Pythagorean Triplet - $A^2$ $+$ $B^2$ $=$ $C^2$.Mostafiz gives an integer $A$. You have to find all the triplets where:

• $A^2$ $+$ $B^2$ $=$ $C^2$; where $A$, $B$ and $C$ all are positive integers.

• $GCD$ of $A$, $B$ and $C$ must be greater than $1$. $i.e.$ $gcd(A,B,C)>1$.

• $A$ is fixed and $B$ $<$ $A^2$

Example: If $A=12$, Triplets are:

$12$ $9$ $15$ $($$gcd$ $=$ $3$$)$

$12$ $16$ $20$ $($$gcd$ $=$ $4$$)$, where all triplets maintain $($$A^2$ $+$ $B^2$ $=$ $C^2$$)$, has $gcd$ greater than $1$, $A$ is fixed and $B$ $<$ $A^2$.

Input

Each test contains multiple test cases. The first line contains a single integer $T(1 \leq T \leq 2*10^4)$ the number of test cases.

Each test case contains a single integer $A$ $($$1$ $\leq$ $A$ $\leq$ $30030$$)$.

Output

For each test case, print one integer $N$ which is the number of triplets that follow all the conditions.

Next $N$ lines, print three integers $A$, $B$ and $C$ in the increasing order of $\bf{B}$ that follows the conditions.

Sample

2
6
12

1
6 8 10
2
12 9 15
12 16 20