NWERC11A  Binomial coefficients
Binomial coefficients
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 coefficients to help him check some of his calculations.
A binomial coefficient is a number
where n and k are nonnegative integers.
Gunnar used his program to calculate 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 find all possible candidates?
Input
On the first 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 ≤ 10^{15}): 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 coefficient.
 one line with all pairs (n,k) that satisfy = 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.
Sample in and output
Input 
Output 
2 2 15 
1 (2,1) 4 (6,2) (6,4) (15,1) (15,14) 
Copyright notice
This problem text is copyright by the NWERC 2011 jury. It is licensed under the Creative Commons AttributionShare Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/bysa/3.0/legalcode
hide comments
nadstratosfer:
20200216 14:15:12
Awesome problem. Totally didn't expect my solution to end up like it did, just kept building up on ideas and observations made while poking at it until I got me a working program. 

Bharath Reddy:
20140406 11:11:35
While printing (6,2) there should be no spaces before or after the 'comma'


Sidharth Gupta:
20120131 21:29:52
test cases are weak. my wrong code got AC!

Added by:  Jeroen Bransen 
Date:  20111102 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  NWERC 2011 Jury 