favorite We need a little bit of your help to keep things running, click on this banner to learn more

DSLCS 2011 Number Theory. Favorites

Send a Table

Jimmy had to calculate a function Answer(x, y) where x and y are both integers in the range [1, n]. When he knows Answer(x, y), he can easily derive Answer(k * x, k * y), where k is any integer from it by applying some simple calculations involving Answer(x, y) and k.

For example if n = 4, he only needs to know the answers for 11 out of the 16 possible input value combinations: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3) and Answer(4, 1). The other 5 can be derived from them (Answer(2, 2), Answer(3, 3) and Answer(4, 4) from Answer(1, 1), Answer(2, 4) from Answer(1, 2) and Answer(4, 2) from Answer(2, 1). Note that the function Answer is not symmetric, so Answer(3, 2) can not be derived from Answer(2, 3).

Now what we want you to do is: for any values of n from 1 up to and including 50000, give the number of function Jimmy has to pre-calculate.


Consists of at most 600 lines. Each line contains an integer less than 50001 that indicate the value of n. Input is terminated by a line that contains one zero. This line should not be processed.


For each input line produce one output line. This line contains an integer which indicates how many values Jimmy has to pre-calculate for a certain value of n.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1