如下图所示，有 个仪器，中间的方块是仪器的主体，每个仪器可以充当接收器或者信号源；主体的左右两侧是两个接线点。 现在，我们将左端 个接线点随机分成 组，每组各含两个点，并将右端 个接线点同样随机分成 组。然后将每组的两个接线点用导线连接。 这样一来，我们就得到了一组封闭的信号线路。具体而言： 信号从任一信号源 出发，通过右侧接线点； 随后，信号通过与右侧接线点连接的导线到达另外一个仪器的左侧接线点，再经过仪器主体到达右侧接线点；此时，如果这个仪器是接收器，那么就视为接收到了信号（注意，接收到信号不会影响信号继续往后传递）。 这个过程持续进行，最终会形成若干个独立的循环。 现在，记 表示在所有接收器均能接收到信号的前提下， 个仪器中作为信号源的最少数量。求解 的方差。 可以证明答案可以表示为一个不可约分数 ，为了避免精度问题，请直接输出整数 作为答案，其中 ， 是满足 的整数。更具体地，你需要找到一个整数 满足 对 取模等于 ，您可以查看样例解释得到更具体的说明。 【提示】 本题中，如果您需要使用到除法的取模，即计算 时， 需要使用公式 得到。例如，计算 ： 4^{-1} & = & \left(4^{M-2} \bmod M\right) \\& = & 748\,683\,265 \\\hline\left(\tfrac{5}{4} \bmod M\right) & = & 5 \times4^{-1} \bmod M \\& = & 5 \times 748\,683\,265 \bmod M \\& = & 748\,683\,266\end{array}"

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：在一行上输入一个整数 代表仪器的数量。

输出描述:

对于每组测试数据，新起一行输出一个整数，表示 的方差对 取模后的结果。