You have recently read about superdromes. Superdromes are those numbers that are palindromic in both binary and decimal representation.

The number represented in binary representation is up to its most significant bit that is \(1\). For example, \(2\) will be represented as \(\{10\}\), \(6\) is represented as \(\{110\}\), and so on.

Your task is to determine the number of superdromes that are less than or equal to \(n\) for provided \(n\).

Input format

• First line: A single integer \(q\) denoting the number of queries
• Next line: \(q\) space-separated integer where the \(i_{th}\) integer is \(n\) for the \(i_{th}\) query

Output format
Print a single integer that represents the number of superdromes that is less than or equal to \(n\) for each query. Print the answer for each query as space-separated integers.

Constraints

\(1 \le q \le 10^5\)

\(1 \le n \le 10^6\)