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\ast 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 100000000)$

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