You need to find the product of the first n factorials, so 1! * 2! * ... * n! modulo p, where p=63303212889375877567328165411288303907410870625225931671654121339922293885519921.

Input

An integer T, denoting the number of testcases (T≤10). Each of the T following lines contains a positive integer, where

n≤ 10^8.

Output

Output T lines, the case number followed by the answer. See the sample output for the correct format!

Example

Input:
7
1
5
100
429
1000
1000000
100000000

Output:
Case 1: 1
Case 2: 34560
Case 3: 30320185692040509343149810686654647278680728299485184027723296362520679295668953
Case 4: 49116522183503229678644619968184124916695876848076217702050317922528502280661110
Case 5: 38310494067749735972957877453766730719859042112664856832928508845605975573300554
Case 6: 59623175509081913319809873890125269865036398088611331352359071382248773213856402
Case 7: 43046234475587180053977224639514165196068475389708692929440906111909653614719387