Một tập hợp được coi là phản nhị phân khi tập hợp đó không có đồng thời 2 số dưới dạng ~m~ và ~2*m~.

Ví dụ, tập hợp ~A = {2, 3, 5, 8, 11, 13}~ là tập hợp phản nhị phân, tập hợp ~B = {2, 3, 5, 6, 8, 11, 13}~ không phải, do nó chứa 2 số ~3~ và ~6~.

Công việc của bạn: tìm độ lớn của tập hợp phản nhị phân lớn nhất bao gồm các số tự nhiên từ ~1~ đến ~N~

Input

Dòng đầu là ~T~ ~(T \le 60)~, số lượng test.

Mỗi dòng tiếp theo là 1 số tự nhiên ~N~ ~(1 \le N \le 100\,000\,000)~

Output

Với mỗi test, in ra 1 dòng là kết quả của test đó

Sample Input

5
11
12
13
14
15

Sample Output

7
8
9
9
10