Dãy số Fibonacci là một dãy số quen thuộc với tất cả các bạn. Dãy số này có công thức truy hồi như sau:

• ~f_0~ ~=~ ~0~.
• ~f_1~ ~=~ ~1~.
• ~f_i~ ~=~ ~f_{i - 1} + f_{i - 2}~ với ~i \ge 2~.

Yêu cầu: Cho một số nguyên dương ~x~. Hãy tìm ~i~ sao cho ~f_i = x~. Nếu có nhiều số ~i~ thỏa mãn, hãy in ra ~i~ lớn nhất. Nếu không tồn tại ~i~ thỏa mãn, hãy in ra ~-1~.

INPUT

• Dòng đầu chứa số nguyên dương ~T~ (~1 \le T \le 1000~) là số bộ test.
• ~T~ dòng sau, mỗi dòng chứa một số nguyên dương ~x~ (~1 \le x \le 10^{12}~).

OUTPUT

~T~ dòng, mỗi dòng là số ~i~ sao cho ~f_i = x~. Nếu không tồn tại ~i~ thỏa mãn, in ra ~-1~.

SAMPLE INPUT

2
2
3

SAMPLE OUTPUT

3
4