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.
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.
For each test case, in a separate line, please output the result of S modulo 29.