Problem

Consider a positive integer X, and let S be the sum of all positive integer divisors of 2005X. Your job is to determine S modulo 29 (the rest of the division of 29).

Take X = 1 for example. The positive integer divisor of 20051 are 1 5 401 2005. Therefore S = 2412, and S modulo 29 is equal to 5.

Input

The input consists of several test cases. Each test case contains a line with the integer X(1 <= X <= 10000000).

A test case of X = 0 indicates the end of input, and should not be processed.

Output

For each test case, in a separate line, please output the result of S modulo 29.

Sample Input

1
10000
0

Sample Output

5
2