Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2286
Sum of Divisors

Time Limit: 2 Seconds      Memory Limit: 65536 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



Author: PAN, Minghao
Source: ZOJ Monthly, January 2005
Submit    Status