Description

For a positive integer $n$, find all pairs of non-negative integers $(x, y)$ such that $x^2+y^2=n$.

Input Format

There are multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the next line contains a positive integer, which is the value of $n$.

Output Format

For each test case, first output a single non-negative integer, representing the number of pairs $(x, y)$ that satisfy the condition. Then output all $(x, y)$ in increasing order of $x$. Separate $x$ and $y$ with a space, and separate different pairs with a newline.

Insert a blank line between different test cases.

6
9
98
987
9876
98765
987654321

2
0 3
3 0
1
7 7
0
0
4
13 314
178 259
259 178
314 13
6
4080 31161
11064 29415
18264 25575
25575 18264
29415 11064
31161 4080

Hint

Constraints: For all testdata, $1\le T\le 10^2,1\le n\le 10^{18}$.

Translated by ChatGPT 5