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.
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})$
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$.