Unit Squares Along a Diagonal

Time limit1sMemory limit128 MB

Summary

Given N, count unordered integer side pairs (a,b) such that a+b-gcd(a,b) equals N, using the diagonal-crossing formula for a grid rectangle.

Level: Medium6 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Problem

$R$ is a rectangle whose side lengths are integers. It can be tiled exactly by unit squares, each with side length $1$ .

Define $f(R)$ as the number of unit squares that one diagonal of the rectangle $R$ passes through. For example, a rectangle with side lengths $2$ and $4$ has $f(R) = 4$ .

Given a natural number $N$ , count the number of rectangles $R$ that satisfy $f(R) = N$ . A rectangle with side lengths $a$ and $b$ is considered the same as one with side lengths $b$ and $a$ .

Input

The first line contains a natural number $N$ ( $0 < N < 10^6$ ).

Output

Print the number of rectangles $R$ satisfying $f(R) = N$ on the first line.

Hint

Think about how to express, using only the two side lengths $a$ and $b$ , the number of unit squares that the diagonal of an $a \times b$ rectangle passes through.

Examples2

Example 1
Input
```
4
```
Expected output
```
4
```
Example 2
Input
```
1
```
Expected output
```
1
```