The problem statement is really simple (the constraints maybe not). You are to write all primes less than 10^9.

Input

There is not input.

Output

To make the problem less output related write out only the 1st, 501st, 1001st, ... 1st mod 500.

Example

Input:

Output:
2
3581
7927
...
999978527
999988747
999999151