Gunnar is a rather old and forgetful researcher. Currently, he is writing an article on social media security, which includes some elements of combinatorics. He has written a program to calculate binomial coefficients to verify some calculations.
The binomial coefficient is a number defined by
where and are non-negative integers.
Gunnar uses his program to calculate and obtains a number as a result. Unfortunately, being forgetful, he forgot the values of and he used as input. These two numbers were the result of long computations and were written on one of the many sheets lying on 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 tests, at most . Each test is given in a single line and contains an integer — the result of Gunnar's program.
For each test, output 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 . 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.