Submit | All submissions | Best solutions | Back to list |

## NWERC11A - 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 non-negative 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

Input:2 2 15Output: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 Attribution-Share Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/by-sa/3.0/legalcode

Added by: | Jeroen Bransen |

Date: | 2011-11-02 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | NWERC 2011 Jury |