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.