Gunnar is quite an elderly and forgetful researcher. Currently, he is writing a paper on security in social networks that involves some combinatorics. He developed a program to calculate binomial coefficients to assist him in verifying some of his calculations.
The binomial coefficient Cnk is a number defined by
where n and k are non-negative integers.
Gunnar uses his program to calculate Cnk and obtains a number m as a result. Unfortunately, being forgetful, he forgot the numbers of n and k he used as input. These two numbers were the result of lengthy computations and were written on one of the many sheets scattered across his desk. Instead of searching through the papers, he decided to reconstruct the numbers n and k from the obtained answer. Can you help him find all possible values?
The first line contains the number of test cases, at most 100. Each test is given in a single line and contains an integer m (2≤m≤1015) — the result of the Gunnar’s program.
For each test, print two lines. The first line should contain the number of ways to express m using the binomial coefficient. The second line should contain all pairs (n,k) such that Cnk=m. Pairs should be sorted in increasing order of n, and in case of equality, in increasing order of k. The output format of pairs is given in the example.