Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
85 - ZOJ Monthly, December 2009 - I
Very Simple Counting

Time Limit: 1 Second      Memory Limit: 32768 KB

Let f(n) be the number of factors of integer n.

Your task is to count the number of i(1 <= i < n) that makes f(i) = f(n).

Input

One n per line (1 < n <= 1000000).

There are 10000 lines at most.

Output

For each n, output counting result in one line.

Sample Input

4
5

Sample Output

0
2

Hint

f(1) = 1, f(2) = f(3) = f(5) = 2, f(4) = 3.


Author: WU, Jun
Source: ZOJ Monthly, December 2009
Submit    Status