DA-S96-CA1-Q3

Time Limit: 1 Second    Memory Limit: 2048 KB

You can find the related question in the CA1.


Input

You can find the related question in the CA1.


Output

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


Sample Input

3
2
1
2
2
4
12212

Sample Output

994
1024
987041
Submit