题目描述

输入格式

你需要在一个测试数据中处理多个新斐波那契数列问题。输入第一行T 表示问题的数量。 接下来T行， 每行一个整数：待求解的x 。

输出格式

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

样例数据

input

2 
9 
123

output

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

数据范围

对于 60% 的测试数据，有 x<=1000000。
对于 100% 的测试数据，有 x<=1000000000、 T<=20。