DA-S96-CA1-Q1

Time Limit: 5 Seconds    Memory Limit: 262144 KB

You can find the related question in the CA1.

Input

You can find the related input format in the CA1.

Output

You should print one integer per line which is the answer to the corresponding test case.

Sample Input

4
1
2
3
100

Sample Output

1
2
2
9828

Submit