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]

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 với N.

Dữ liệu vào

Dòng đầu tiên là số T.
T dòng sau, mỗi dòng là 1 số N.

Kết quả

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