23

Bugland has a mixed population: bugs with $2$ antennas and bugs with $3$ antennas.

Clearly, the bugs with $2$ antennas count in base $2$ (they also consider that there are $10$ types of bugs in Bugland), and the bugs with $3$ antennas count in base $3$.

A number is considered improper if the sum of the digits is different in the eyes of the two species of bugs. In other words, a number is considered improper if the sum of the digits of the number written in base $2$ is not the same as the sum of the digits of the number written in base $3$.

In order to promote the equality of the two species of bugs, improper numbers are forbidden.

Task

Considering that the bugs know how to count only from $1$ to $N$, how many allowed numbers exist?

Input data

The first line will contain the number $T$ of scenarios.

The next $T$ lines each contain one number $N$, the highest number the bugs know to count to. Please note that the bugs only know positive integer numbers.

Output data

The first line will contain $T$ numbers, separated by spaces, the $i^{th}$ number representing the answer to the $i^{th}$ scenario.

Constraints and clarifications

• $1 \leq T \leq 1 \ 000$;
• $1 \leq N_i \leq 10^7$;
• For tests worth $20$ points: $1 \leq \sum N_i \leq 10^6$.
• For other tests worth $30$ points: $1 \leq N_i \leq 10^6$.

Example

stdin

10
1 2 3 4 5 6 7 8 9 10

stdout

1 1 1 1 1 2 3 3 3 4

Explanation

The numbers from $1$ to $10$ are written in base $2$ and base $3$ like this:

Therefore, the only allowed numbers are: $1$, $6$, $7$, $10$.