Problem E
Rasterized Lines

Tomáš is a computer graphics student. He has a homework which is very easy for him. He is supposed to make a program that draws a line from point $(0, 0)$ to $(a, b)$, where $a$ and $b$ are positive integers given as the input.

He uses the following algorithm. He divides the plane into squares $1\times 1$ – these squares are pixels. When the line from $(0, 0)$ to $(a, b)$ intersects a square in more than one point, the square (pixel) will be painted black and otherwise it will be painted white.

Figure 1: An example of an output of Tomáš’ algorithm

Tomáš did his homework in 30 minutes and now he is interested in a slightly different problem. Given an integer $N$, for how many different inputs does his algorithm produce exactly $N$ black pixels?

More precisely, he is only interested in lines beginning in $(0, 0)$ and ending in ($a$, $b$), where both $a$ and $b$ are positive integers. Given $N$, find out how many of these lines will produce exactly $N$ black pixels.

Input

The first line of the input file contains an integer $1 \le T \le 60$ specifying the number of test cases.

Each test case looks as follows. The one and only line contains a positive integer $N$, $1 \le N \le 10^{14}$. You can assume that number $N$ has at most $50$ divisors.

Output

For each test case output one line with one integer – the number of lines that use exactly $N$ black pixels.

2
2
6

3
11