Năm ngoái Conan chỉ mới bước vào học Tin học thật sự. Thế nhưng anh ta bị đàn em là Như Quỳnh thách đố bài toán sau:

Cho ~T \leq 100000~. Mỗi dòng của ~T~ có ~1~ số ~N~ ~(N \leq 100000)~. Dãy số ~A~ được xây dựng như sau:

• ~A_{0} = 0~
• ~A_{1} = 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 là số ~T~.
• ~T~ dòng sau, mỗi dòng là ~1~ số ~N~.

Output

• Có ~T~ dòng tương ứng với giá trị lớn nhất của các đoạn.

Sample Input

2
5
10

Sample Output

3
4