Box

Gorwin 是一个女神，但是Vivin 是一个屌丝。 Vivin 已经暗恋Gorwin很久了。 Vivin 相信屌丝总有逆袭的一天。 今天是情人节，Vivin鼓起了勇气去和Gorwin约会了。在约会的过程中，他们玩了一个游戏。地上有$2n$个大小相同的立方体箱子，Gorwin和Vinvin每各自拿$n$个箱子去推一个高$n$个箱子的塔。他们将花$2n$秒来完成这个游戏。每一秒中，只有一个人可以拿一个箱子去叠到自己的塔上。根据女士优先原则，Vinvin的塔在任何时刻不能高于Gorwin的。请计算一下有多少种不同的操作序列可以完成游戏。答案很大，对$3814697265625$取模输出即可。

多组测试数据，在文件的第一行输入一个$T$，代表有$T$组测试数据。
接下来的$T$行，每一行给一个整数$n$。

[参数说明]
所有输入为整数。
$0< T <= 20,1<=n<=1000000000000000000({10}^{18})$

对每一个数据，输出占一行，输出格式是Case #id: ans,这里id是数据编号，从1开始；ans是答案对$3814697265625$取模的结果。
看样例可以得到更多信息。

2
1
2

Case #1: 1
Case #2: 2

对第一个样例，只有一种方法，第一步Gorwin先拿一个箱子堆到自己的塔上，然后Vinvin拿一个。第一步Vinvin不能先拿，因为如果这样的话，他的塔就会比Gorwin高了。
对于第二个样例有两种方法。
方法1：第一步Gorwin拿一个箱子；第二步Gorwin拿一个箱子；第三步Vinvin拿一个箱子；
第四步Vinvin拿一个箱子；
方法2：第一步Gorwin拿一个箱子；第二步Vinvin拿一个箱子；第三步Gorwin拿一个箱子；
第四步Vinvin拿一个箱子；
没有其它的方法可以完成这个游戏，所以方法数目是2。