Problem Description

Gorwin is a Goodness while Vivin is a Dios. Vivin has hidden to love Gorwin for long time. Vivin believes that Dios will one day get a counter attack. Today is Valentines' Day, Vivin gets up the encourage to make an engagement with Gorwin. During the dating, they play a game. There are $2n$ cube boxes of the same size on the ground, Gorwin and Vinvin will take $n$ boxes respectively and then pile a tower of $n$ boxes. They will take $2n$ seconds to pile the towers. In each second, only one people can take exact a box and pile it to his/her own tower. However, according to the doctrine of “lady first”, the height of Vinvin’s tower should not be higher than Gorwin’s during every second in the game.

You are expected to write a program to calculate how many different operation sequences to complete the game. For the answer may be very large, please output the answer modular $3814697265625$ instead.

Input

There are multiple test cases. In the first line of the input file there is an integer $T$ indicates the number test cases.
In the next $T$ lines, each line contains an integer $n$ which is mentioned above.

[Technical Specification]
All input items are integers.
$0< T <= 20, 1<=n<=1000000000000000000({10}^{18})$

Output

For each case，the output should occupies exactly one line. The output format is Case #id: ans, here id is the data number starting from 1; ans is the result of answer modular $3814697265625$.

2
1
2

Case #1: 1
Case #2: 2

Hint

For the first case, the is only one way to accomplish the game, i.e. step 1, Gorwin piles one box to her tower; step 2 Vinvin piles the last box to his tower. Because Vinvin’s tower should not be higher than Gorwin’s in every second during the game, so step 1 Vinvin can’t take a box to pile to his tower.

For the second case,
Way 1: step1 Gorwin piles one box; step2 Gorwin piles one box; step3 Vinvin piles one box; step4 Vinvin piles one box;
Way 2: step1 Gorwin piles one box; step2 Vinvin piles one box; step3 Gorwin piles one box; step4 Vinvin piles one box.
There is no other valid way to realize the game. So the answer to the second case is 2.