Cho số nguyên dương ~X~ và dãy ~Gabonacci~ được tính bởi công thức truy hồi: ~G_i = G_{i-1} + G_{i-2}~ ~(i > 2)~.

Cần chọn ~2~ số ~G_1~ và ~G_2~ nhỏ nhất có thể để ~X~ xuất hiện trong dãy ~Gabonacci~, tính ~2~ giá trị nhỏ nhất này.

Cặp số ~(a, b)~ được gọi là lớn hơn ~(a', b')~ nếu ~b > b'~ hoặc ~b = b'~ và ~a > a'~.

Ví dụ với ~X = 89~: một số cách chọn cặp ~(G1, G2)~ là ~(1, 1), (1, 88), (8, 13), ...~ trong đó cặp ~(1, 1)~ là nhỏ nhất.

Input

Dòng đầu tiên chứa số nguyên dương ~Q~ là số truy vấn ~(1 \le Q \le 10^5)~.

Trong số ~Q~ dòng sau, mỗi dòng chứa một số nguyên dương ~X~ ~(2 \le X \le 10^9)~.

Output

Gồm ~Q~ dòng, dòng ~i~ là kết quả của truy vấn thứ ~i~ ~(1 \le i \le Q)~.

Sample Input 1

4
89
123
842831057
1000

Sample Output 1

1 1
1 3
2 7
2 10