sqrt log sin

An evil professor has just assigned you the following problem. A sequence is defined by the following recurrence:

For each value $i$ compute the value $x_i$.

Input

Consists of a number of lines, each containing one integer $i$, no less than $0$ and no greater than $10^6$. Input is followed by a single line containing the integer $-1$. This last line is not a value of $i$ and should not be processed.

Output

For each value of $i$ (but not the final $-1$) output the corresponding value of $x_i$ modulo $10^6$.

Examples