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:
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.
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.
For each test case output one line with one integer – the number of lines that use exactly N black pixels.
Input:
2 2 6
Output:
3 11
In the first test case, the three good lines are those ending in (1,2), (2,1), and in (2,2).
Credits:
Problemsetter(s):lukas
Contest-related materials: lukas, mino