Kattis

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

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.

Sample Input 1 Sample Output 1
2
2
6

3
11