Orange的连线游戏

题目描述

Orange想到了一个连线游戏，首先，Orange会给你一个数字 $n$，代表一共有 $2n$ 个不同的数，Orange会将他们排列成一个圆环形，你需要用直线连接两个数，使得每个数都有且仅被连接过一次，且圆环内直线互不相交。你需要告诉Orange共有多少种不同的连接方案。

两种连接方案不同指的是至少有一对由直线连接的2个数不同。

输入格式

输入共有 $T + 1$ 行，$T(T \leq 2 \times 10^5)$ 表示测试用例的数量，每组测试用例占一行，为一个整数 $n(n \leq 100)$，表示Orange给你的数。

输出格式

输入共有 $T$ 行，表示每个测试用例的答案。

样例 #1

样例输入 #1

2
1
2

样例输出 #1

1
2

提示

对于样例2，共有4个整数，排列成圆环如下：

1 2

3 4

方案如下：

1. 1-2，3-4
2. 1-3，2-4

不存在更多的合法方案，因此答案为2.