Binomial coefficients#4008
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 C_n^{k} is a number defined by
where and are non-negative integers.
Gunnar uses his program to calculate C_n^{k} and obtains a number as a result. Unfortunately, being forgetful, he forgot the numbers of and 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 and from the obtained answer. Can you help him find all possible values?
The first line contains the number of test cases, at most . Each test is given in a single line and contains an integer m~(2 \le m \le 10^{15}) — the result of the Gunnar’s program.
For each test, print two lines. The first line should contain the number of ways to express using the binomial coefficient. The second line should contain all pairs such that C_n^{k} = m. Pairs should be sorted in increasing order of , and in case of equality, in increasing order of . The output format of pairs is given in the example.
Пример 1