Giải bài trực tuyến

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

Example

Input
2
5
10

Output
3
4