Sum of Divisors

Time Limit: 1 Second    Memory Limit: 32768 KB

For an integer n, define f(n) to be the sum of its proper divisors (the divisors excluding the number itself), f is called the restricted divisor function.

Given an integer m. Find how many integers n between 1 and 1000000 (inclusively) has f(n)<=m.

Input

The input contains several cases, each has a single integer m on a seperate line. All input data fit in a signed 32-bit integer.

Output

The answer for each case should be printed on a seperate line.

Sample Input

1
3392927
3392928

Sample Output

78499
999999
1000000

Submit

Source: ZOJ Monthly, January 2005