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 10^5~ dòng, mỗi dòng của ~t~ có 1 số nguyên ~n~ (~n \leq 10^5~).

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]~

Yêu cầu

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

Input

• Dòng đầu tiên ghi số nguyên dương ~t~.
• ~t~ dòng sau, mỗi dòng là một 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 Test

Input

2
5
10

Output

3
4