Internet Problem Solving Contest

IPSC 2007

Problem R – Rasterized Lines

Tomas is a computer graphics student. He has a homework which is very easy for him. He has to make a program that draws a line from point (0, 0) to (a, b), where integers a, b (a>0, b> 0) are the input of the program.

He uses the following algorithm. He divides the plane into squares 1x1 – 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 black. Otherwise it will be white. Look at the example:

Problem specification

Tomas 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 specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case looks as follows: The one and only line contains a positive integer N. You can assume that number N has at most 47 divisors.

Output specification

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








In the first test case, the three good lines are those ending in (1,2), (2,1), and in (2,2).

Contest-related materials: lukas, mino