Description

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中的数列，以比利时数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,……
卡特兰数k(n)有如下递推关系：
令k(0)=1;

你的任务是求第n个卡特兰数。

Input

第一行输入一个整数T(T≤100)表示测试数据组数。
之后每行输入一个整数n(n≤100)。

Output

对于每组测试数据，输出一个整数表示第n个卡特兰数。

Sample Input

2
1
10

Sample Output

1
16796

HINT

Source

NBU OJ