# 23

##### Output:

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.

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:

base $10$ base $2$ base $3$ the sum in base $2$ the sum in base $3$
1 1 1 1 1
2 10 2 1 2
3 11 10 2 1
4 100 11 1 2
5 101 12 2 3
6 110 20 2 2
7 111 21 3 3
8 1000 22 1 4
9 1001 100 2 1
10 1010 101 2 2

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

## Problem info

ID: 1613

Editor: stefdasca

Author:

Source: IIOT 2019-20 Round I

Tags: