Problem E
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_{k-1}}$,

• $CP_ i$ is a positive integer.

A sequence is called CP-sequence if it satisfies the above conditions. For example:

• $1, 2, 4, 8, 16$ is a CP-sequence.

• $4, 6, 9$ is a CP-sequence.

• $4, 2, 1$ is NOT a CP-sequence, because $4 > 2$.

• $4, 6, 9, 13.5$ is NOT a CP-sequence, because $13.5$ is not an integer.

• $4, 6, 9, 13$ is NOT a CP-sequence, because $\frac{13}{9} \ne \frac{9}{6}$.

Bash is very excited to learn about CP-sequences. Given an integer $S$, he wants to know how many CP-sequences there are whose sum equals $S$.

For example, when $S = 7$, there are $5$ CP-sequences: $(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}$.

7
3 5 7 11 13 17 19

2 3 5 6 8 9 11