Dãy số ~A~ được xây dựng như sau:

• ~A_0 = 0~
• ~A1 = 1~
• ~A_{2i} = A_i~
• ~A_{2i + 1} = A_i + A_{i + 1}~

Nhiệm vụ của bạn là tìm số lớn nhất của dãy ~A~ từ ~1~ với ~N~.

Input

Dòng đầu tiên ghi số nguyên dương ~T (1 \le T \le 10^5)~ là số bộ test.

~T~ dòng tiếp theo, mỗi dòng ghi số nguyên dương ~N (1 \le N \le 10^5)~.

Output

Gồm ~T~ dòng, mỗi dòng ghi duy nhất ~1~ số nguyên dương là kết quả của bài toán.

Sample

Input #1

2
5
10

Output #1

3
4