Dzidzio and the planet Olympia

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Megapopular Dzidzio visited the planet Olympia, where many sports fans live. Weightlifting is the most popular among the inhabitants of Olympia. Dzidzio, an ardent fan of this sport, has repeatedly been a judge at competitions.

Interestingly, this planet also has very strange rules for calculating the sum of two numbers. Thus, the sum of two numbers is considered to be the least common multiple of these numbers. The least common multiple of natural numbers \(a\) and \(b\) is the smallest natural number that is divisible evenly by \(a\) and \(b\), meaning the sum of 2 and 4 is not 6 at all, but 4. In weightlifting, the rules for determining the winner are quite simple: there are two exercises, for each of which certain points are given in the form of a positive integer. Whoever has the larger sum of these points wins.

Once during a weightlifting competition, Dzidzio managed to record only the sum \(x\) of the winner. Now he is interested in how many such pairs of numbers exist that in sum (according to the rules of the planet Olympia) give the number \(x\).

Input

The first and only line contains a single integer \(x\) — the sum of the athlete’s two-event total.

Output

In a single line, print a single integer — the answer to the problem.

Constraints

20% of tests: \(1 \le x \le 10^2\),

40% of tests: \(1 \le x \le 10^4\),

40% of tests: \(1 \le x \le 10^7\).

Samples

Input (stdin) сopy	Output (stdout) сopy
47	3

Input (stdin) сopy	Output (stdout) сopy
6	9

Notes

In the second example, there are 9 pairs: \((1 , 6)\), \((2 , 6)\), \((3 , 6)\), \((6 , 3)\), \((6 , 2)\), \((6 , 1)\), \((2 , 3)\), \((3 , 2)\), \((6 , 6)\).