HHPC1 P4 - Yet Another A+B Problem

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Ryan is completing his math assignment where he stumbles upon a curious problem: find the number of pairs of positive integers (a,b) that satisfy the equation \frac{1}{a} + \frac{1}{b} = \frac{1}{2}. The assignment is too easy for him, so he generalises the problem: find the number of ordered pairs of positive integers (a,b) which satisfy \frac{1}{a} + \frac{1}{b} = \frac{1}{c} for a given positive integer c.

Can you help Ryan solve this redesigned math problem?


For all subtasks:

1 \leq T \leq 10^5

1 \leq c \leq 10^7

Subtask 1 [5%]

c = 2

Subtask 2 [45%]

1 \leq T \leq 10^3

1 \leq c \leq 5 \times 10^4

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains a single integer T, the number of test cases.

The following T lines each contain a single integer c.

Output Specification

For each test case, print a single integer, the number of ordered positive integer pairs (a,b) that satisfy \frac{1}{a}+\frac{1}{b}=\frac{1}{c}. It can be proven that the answer can fit in a 64-bit signed integer.

Sample Input


Sample Output


Sample Explanation

For the first test case, only (2,2) satisfies the condition.

For the second test case, (4,12), (6,6) and (12,4) satisfy the condition.


There are no comments at the moment.