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