# Binomial Coefficients

Time Limit: 10 Seconds    Memory Limit: 65536 KB

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 coefﬁcients to help him check some of his calculations. A binomial coefﬁcient is a number (kn) = n! / k!(n-k)! where n and k are non-negative integers.

Gunnar used his program to calculate (kn) 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 ﬁnd all possible candidates?

## Input

On the ﬁrst line a positive integer: the number of test cases, at most 100. After that per test case:

one line with an integer m (2 ≤ m ≤ 1015): the output of Gunnar’s program.

## Output

Per test case:

one line with an integer: the number of ways of expressing m as a binomial coefﬁcient.

one line with all pairs (n, k) that satisfy (kn) = 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.

```2
2
15```

## Sample Output

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

Source: NWERC 2011