Binomial coefficients

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 $n$ and $k$ are non-negative integers.

Gunnar uses his program to calculate $C_n^k$ 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?

Input

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\le m\le 10^{15})$ — the result of the Gunnar’s program.

Output

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 $C_n^k=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.

Examples