Limits 1s, 64 MB

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 - A2A^2 ++ B2B^2 == C2C^2.Mostafiz gives an integer AA. You have to find all the triplets where:

  • A2A^2 ++ B2B^2 == C2C^2; where AA, BB and CC all are positive integers.

  • GCDGCD of AA, BB and CC must be greater than 11. i.e.i.e. gcd(A,B,C)>1gcd(A,B,C)>1.

  • AA is fixed and BB << A2A^2

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

1212 99 1515 ((gcdgcd == 33))

1212 1616 2020 ((gcdgcd == 44)), where all triplets maintain ((A2A^2 ++ B2B^2 == C2C^2)), has gcdgcd greater than 11, AA is fixed and BB << A2A^2.

Input

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

Each test case contains a single integer AA ((11 \leq AA \leq 3003030030)).

Output

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

Next NN lines, print three integers AA, BB and CC in the increasing order of B\bf{B} that follows the conditions.

Sample

InputOutput
2
6
12
1
6 8 10
2
12 9 15
12 16 20

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.