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ố \(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\) tớ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

2
5
10

3
4

Nguồn: vn.spoj