Gunnar 是一位年迈且健忘的研究员。目前他正在撰写一篇关于社交网络安全的论文，其中涉及了一些组合数学的内容。他编写了一个计算二项式系数的程序，以帮助他核对部分计算结果。

二项式系数是一个数，定义为：

$$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$

其中 $n$ 和 $k$ 是非负整数。

Gunnar 使用他的程序计算了 $\binom{n}{k}$ 并得到了结果 $m$。不幸的是，由于他很健忘，他忘记了作为输入的 $n$ 和 $k$。这两个数是一项长期计算的结果，写在他桌上堆积如山的纸张中的某一张上。与其费力寻找这些纸张，他尝试根据得到的输出 $m$ 来重构 $n$ 和 $k$。你能帮他找出所有可能的候选值吗？

输入格式

第一行包含一个正整数：测试用例的数量，最多为 $100$。之后每个测试用例包含：

• 一行包含一个整数 $m$ ($2 \le m \le 10^{15}$)，即 Gunnar 程序输出的结果。

输出格式

对于每个测试用例：

• 第一行输出一个整数：将 $m$ 表示为二项式系数的方法总数。
• 第二行输出所有满足 $\binom{n}{k} = m$ 的数对 $(n, k)$。按 $n$ 的升序排列；若 $n$ 相同，则按 $k$ 的升序排列。格式参考样例输出。

样例

输入 1

2
2
15

输出 1

1
(2,1)
4
(6,2) (6,4) (15,1) (15,14)