Killjee has recently read about superdromes. Superdromes are those numbers which are palindromic in both binary and decimal representation.

The number represented in binary representation will be up to its most significant bit which is 1.

For example, 2 will be represented as {10}, 6 will be represented as {110} and so on.

Now killjee ask you to find number of Superdromes less than or equal to n for given n.

INPUT FORMAT

First line of input contains a single integer q, denoting number of queries.
Next line contains q space separated integer, $i_{th}$ integer is n for $i_{th}$ query.

OUTPUT FORMAT

Output a single integer, number of Superdromes $\le n$ for each query. Print answer for each query in new line.

INPUT CONSTRAINTS

• $1 \le q \le 10^5$
• $1 \le n \le 10^6$