Conan đang quậy, anh ta muốn làm khó mọi người. Vì thế anh ta nghĩ ra ~1~ trò mới, đó là đố mọi người một bài khó hơn, đề bài MAXARR1, với các giới hạn mới là ~T \le 10000~ và ~N \le 10^{18}~.

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~. Mỗi dòng của ~T~ có ~1~ số ~N~. 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