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:

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$.