Quantum algorithms can speed up finding the minimum element in a random sequence.
Given a prime , you need to find all the such that , where is the modular inverse of such that .
Since and don't support int128, the limit of this problem is and you need to solve 500 cases.

输入描述:

The first line contains an integer , indicating the number of test cases.
Each of the following T lines contains a prime .
To make the problem more unserious, the given prime in each test case is chosen in all primes in  uniformly at random.

输出描述:

For each test case, output one integer n in the first line - the number of  that satisfy  and .
Then output two integers  and  in the -th of the following  lines in ascending order of .

4
2
3
5
7

0
1
2 2
2
2 3
3 2
2
2 4
4 2