問題文

二つの自然数 a, b に対して、うく数列を以下のように定義する。

u_1 = a, u_2 = b, u_{k+2} = u_k + u_{k+1} (1 \leq k)

2 以上の自然数 X_i がT 個与えられるので、各 X_i に対し、X_i を含むようなうく数列の中で辞書順最小のものを求めるプログラムを作成せよ。

制約

• 1 \leq T \leq 100
• 2 \leq X_i \leq 10^{18}
• 入力は全て整数

入力例 1

3
14
233
100

出力例 1

1 4
1 1
1 99

a = 1, b = 4 のとき、うく数列は以下のようになる

{1, 4, 5, 9, 14, ..}