Gunnar is quite an old and forgetful researcher. Right now he is writing a paper on security in social networks and it actually involves some combinatorics. He wrote a program for calculating binomial coefficients to help him check some of his calculations.

A binomial coefficient is a number

$${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!},}$$

where $n$ and $k$ are non-negative integers.

Gunnar used his program to calculate $(\genfrac{}{}{0ex}{}{n}{k})$ and got a number $m$ as a result. Unfortunately, since he is forgetful, he forgot the numbers $n$ and $k$ he used as input. These two numbers were a result of a long calculation and they are written on one of many papers lying on his desk. Instead of trying to search for the papers, he tried to reconstruct the numbers $n,k$ from the output he got. Can you help him and find all possible candidates?

Input Specification

On the first line a positive integer: the number of test cases, at most $100$.

After that, per test case: one line with an integer $m$ $(2\le m\le {10}^{15})$: the output of Gunnar's program.

Output Specification

Per test case:

• one line with an integer: the number of ways of expressing $m$ as a binomial coefficient.
• one line with all pairs $(n,k)$ that satisfy $(\genfrac{}{}{0ex}{}{n}{k})=m$. Order them in increasing order of $n$ and, in case of a tie, order them in increasing order of $k$. Format them as in the sample output.

Sample Input

2
2
15

Sample Output

1
(2,1)
4
(6,2) (6,4) (15,1) (15,14)