说明

翟某人的数据结构学的一塌糊涂，有个问题她整不明白了，你得帮她。

假设有一个栈，同时假设有n个元素构成的序列，这些元素的排列顺序是固定给你的。

通过不同进栈，出栈的操作顺序可以得到不同的序列。

比如说，3个元素的序列1,2,3.

~可以通过  push(1),push(2),pop(),push(3),pop(),pop() 得到序列 2,3,1；

~可以通过  push(1),push(2),push(3)pop(),pop(),pop() 得到序列 3,2,1；

类似的，一共可以得5种不同的序列。

现在告诉你序列中元素的个数n，你告诉翟某人在一个队列里操作这个元素序列进队出队会得到几种序列？

输入格式

第一行输入一个数 t,表示有t组数据；

接下来 t 行，每行一个数 n, 表示序列中元素的个数。

输出格式

对于第i组数据，输出答案

Case i: x

其中 x为能得到的序列个数。

每2组数据之间输出一个空行；

样例

1
1

Case 1: 1

样例

2
1
1

Case 1: 1

Case 2: 1

提示

不要多输出空行。

数据不多，不用long.