Evolutions
In order to become the very best Pokenom trainer, Bash is studying Pokenom’s evolutions.
Each Pokenom has a combat power ($CP$), indicating how strong the Pokenom is. After certain amount of training, a Pokenom can evolve, and the evolved Pokenom will have higher $CP$. A Pokenom can evolve multiple times. There is no known limit on how many times a Pokenom can evolve.
When a Pokenom evolves, his $CP$ always increases by a constant ratio.
More formally, let’s $CP_ i$ denotes the $CP$ of the Pokenom after it evolved $i$ times. If the Pokenom evolves $k$ times, then the following conditions must be true:

$CP_0 < CP_1$ or $k < 1$,

$\frac{CP_1}{CP_0} = \frac{CP_2}{CP_1} = \cdots = \frac{CP_ k}{CP_{k1}}$,

$CP_ i$ is a positive integer.
A sequence is called CPsequence if it satisfies the above conditions. For example:

$1, 2, 4, 8, 16$ is a CPsequence.

$4, 6, 9$ is a CPsequence.

$4, 2, 1$ is NOT a CPsequence, because $4 > 2$.

$4, 6, 9, 13.5$ is NOT a CPsequence, because $13.5$ is not an integer.

$4, 6, 9, 13$ is NOT a CPsequence, because $\frac{13}{9} \ne \frac{9}{6}$.
Bash is very excited to learn about CPsequences. Given an integer $S$, he wants to know how many CPsequences there are whose sum equals $S$.
For example, when $S = 7$, there are $5$ CPsequences: $(7), (1, 6), (2, 5), (3, 4), (1, 2, 4)$. When $S = 19$, there are $11$ sequences: $(19), (1, 18), (2, 17), \ldots , (9, 10), (4, 6, 9)$.
Input

The first line contains one integer $t$ $(1 \leq t \leq 1\, 000)$.

The second line contains $t$ distinct integers $S_{1}, S_{2}, \ldots , S_{t}$ $(1 \leq S_{i} \leq 10^{6}~ \forall 1 \leq i \leq t)$.
Output
Print $t$ integers in one line, the $i$th number should be the answer to the problem when $S = S_{i}$.
Sample Input 1  Sample Output 1 

7 3 5 7 11 13 17 19 
2 3 5 6 8 9 11 