ICPC Asia Jakarta 2020 Official Team Training 4 (19 Dec)


2020-12-18 17:00 AKST

ICPC Asia Jakarta 2020 Official Team Training 4 (19 Dec)


2020-12-18 22:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -398 days 6:10:28

Time elapsed


Time remaining


Problem M
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.

\includegraphics[width=0.5\textwidth ]{obrazok.pdf}
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.


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.


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