Migrated from Lutece 134 Hotel

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A new hotel has been built in a city where the citizens believe that the number $13$ brings bad luck. The hotel has $n$ rooms which are numbered from $1$ to $n$ inclusive. One of the main properties of a room is its unlucky value which depends on the room number. Only number whose decimal forms contain the substring 13 will be considered to be unlucky numbers. For example, $13$, $132$, $1313$, $9130$ are unlucky numbers, but $1$, $3$, $31$, $103$, $123123$ are not. The unlucky value of a room is the square of the room number if the room number is unlucky, and zero otherwise.

A hotel's unlucky value equals the sum of the unlucky value of all its rooms. Help the manager to calculate the unlucky value of this hotel.

Input

The first line contains an integer $T$ ($T\leq 100$) indicating the number of test cases. $T$ lines follows, each line contains an integer $k$ ($1\leq k\leq 100$) indicating that this hotel has $10^k$ (the $k_{th}$ power of $10$) rooms.

Output

For each test case, print the case number and the answer mod $100003$ in a single line where the answer is the unlucky value of this hotel. Follow the format of the sample output please.

Samples

3 
1 
2 
3

Case 1: 0 
Case 2: 169 
Case 3: 49582

Resources

The 5th Guangting Cup Central China Invitatio