题目描述

给定正整数 $a(a\ge1)$，新斐波那契数列 $f_a$ 按如下方式定义：

• $f_a(1) = 1$；
• $f_a(2) = a$；
• $f_a(n) = f_a(n − 1) + f_a(n − 2)\ (n > 2)$。

例如，给定 $a = 4$，有 $f_4(1) = 1, f_4(2) = 4, f_4(3) = 5, f_4(4) = 9, f_4(5) = 14, \cdots$ 现在已知新斐波那契数列中的一项 $x$，但并不知道 $n$ 和 $a$ 的值是多少。请你求出所有可能的 $n,a(n\ge2)$ 满足 $f_a(n) = x$。

输入格式

你需要在一个测试数据中处理多个新斐波那契数列问题。输入第一行 $T$ 表示问题的数量。

接下来 $T$ 行， 每行一个整数：待求解的 $x$。

输出格式

对于每个新斐波那契数列问题，按照 $n$ 从小到大的顺序，输出所有可能的 $n,a$ 满足 $f_a(n) = x$。每行输出一对 $n$ 和 $a$，由一个空格分隔。

2
9
123

2 9
3 8
4 4
2 123
3 122
4 61
6 24
10 3

提示

对于 $60\%$ 的测试数据，有 $1\le x\le10^6$。

对于 $100\%$ 的测试数据，有 $2\le x\le10^9,1\le T\le20$。

本题原始满分为 $15\text{pts}$。