CF1739C.Card Game

Consider a game with $n$ cards ($n$ is even). Each card has a number written on it, between $1$ and $n$. All numbers on the cards are different. We say that a card with number $x$ is stronger than a card with number $y$ if $x \gt y$.

Two players, Alex and Boris, play this game. In the beginning, each of them receives exactly $\frac{n}{2}$ cards, so each card belongs to exactly one player. Then, they take turns. Alex goes first, then Boris, then Alex again, and so on.

On a player's turn, he must play exactly one of his cards. Then, if the opponent doesn't have any cards stronger than the card played, the opponent loses, and the game ends. Otherwise, the opponent has to play a stronger card (exactly one card as well). These two cards are removed from the game, and the turn ends. If there are no cards left, the game ends in a draw; otherwise it's the opponent's turn.

Consider all possible ways to distribute the cards between two players, so that each of them receives exactly half of the cards. You have to calculate three numbers:

• the number of ways to distribute the cards so that Alex wins;
• the number of ways to distribute the cards so that Boris wins;
• the number of ways to distribute the cards so that the game ends in a draw.

You may assume that both players play optimally (i. e. if a player can win no matter how his opponent plays, he wins). Two ways to distribute the cards are different if there is at least one card such that, in one of these ways, it is given to Alex, and in the other way, it is given to Boris.

For example, suppose $n = 4$, Alex receives the cards $[2, 3]$, and Boris receives the cards $[1, 4]$. Then the game may go as follows:

• if Alex plays the card $2$, then Boris has to respond with the card $4$. Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is $1$; he plays it, and Alex responds with the card $3$. So, the game ends in a draw;
• if Alex plays the card $3$, then Boris has to respond with the card $4$. Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is $1$; he plays it, and Alex responds with the card $2$. So, the game ends in a draw.

So, in this case, the game ends in a draw.

考虑一个包含 $n$ 张卡片的游戏（$n$ 为偶数）。每张卡片上写有一个介于 $1$ 到 $n$ 之间的整数，且所有卡片上的数字互不相同。我们称数字为 $x$ 的卡片强于数字为 $y$ 的卡片，当且仅当 $x \gt y$。

两名玩家 Alex 和 Boris 进行此游戏。游戏开始时，每人恰好获得 $\frac{n}{2}$ 张卡片，即每张卡片恰好属于其中一名玩家。随后，他们轮流行动：Alex 先手，接着是 Boris，然后是 Alex，依此类推。

在某位玩家的回合中，他必须恰好打出自己手中的一张卡片。紧接着，若对手手中没有任何比该打出卡片更强的卡片，则对手立即输掉游戏，游戏结束；否则，对手必须打出一张更强的卡片（也恰好一张）。这两张卡片将从游戏中移除，当前回合结束。若此时双方手中均无剩余卡片，则游戏以平局结束；否则，轮到对手行动。

考虑所有可能的发牌方式（即把 $n$ 张卡片平均分给两名玩家，每人 $\frac{n}{2}$ 张）。

你需要计算以下三个数值：

• 使得 Alex 获胜的发牌方式数目；
• 使得 Boris 获胜的发牌方式数目；
• 使得游戏以平局结束的发牌方式数目。

你可以假设双方均采用最优策略（即：若某位玩家存在一种策略，使其无论对手如何应对都能获胜，则该玩家必胜）。两种发牌方式被视为不同，当且仅当存在至少一张卡片，在这两种方式中被分配给了不同的玩家。

例如，设 $n = 4$，Alex 拿到卡片 $[2, 3]$，Boris 拿到卡片 $[1, 4]$。则游戏可能按如下方式进行：

• 若 Alex 打出卡片 $2$，则 Boris 必须以卡片 $4$ 应对。Alex 的回合结束，轮到 Boris 行动。此时 Boris 手中仅剩卡片 $1$；他打出 $1$，Alex 以卡片 $3$ 应对。因此游戏以平局结束；
• 若 Alex 打出卡片 $3$，则 Boris 必须以卡片 $4$ 应对。Alex 的回合结束，轮到 Boris 行动。此时 Boris 手中仅剩卡片 $1$；他打出 $1$，Alex 以卡片 $2$ 应对。因此游戏以平局结束。

因此，在本例中，游戏以平局结束。

The first line contains one integer $t$ ($1 \le t \le 30$) — the number of test cases.

Then, $t$ lines follow. The $i$-th line contains one even integer $n$ ($2 \le n \le 60$).

第一行包含一个整数 $t$（$1 \le t \le 30$）—— 测试用例的数量。

接下来有 $t$ 行。第 $i$ 行包含一个偶数 $n$（$2 \le n \le 60$）。

For each test case, print three integers:

• the number of ways to distribute the cards so that Alex wins;
• the number of ways to distribute the cards so that Boris wins;
• the number of ways to distribute the cards so that the game ends in a draw.

Since the answers can be large, print them modulo $998244353$.

对每个测试用例，输出三个整数：

• 使得 Alex 获胜的发牌方案数；
• 使得 Boris 获胜的发牌方案数；
• 使得游戏以平局结束的发牌方案数。

由于答案可能很大，请对 $998244353$ 取模后输出。

In the first test case, Alex wins if he receives the card $2$ (he plays it, and Boris cannot respond). If Alex receives the card $1$, the game ends in a draw.

In the second test case:

• Alex wins if he receives the cards $[3, 4]$, $[2, 4]$ or $[1, 4]$;
• Boris wins if Alex receives the cards $[1, 2]$ or $[1, 3]$;
• the game ends in a draw if Alex receives the cards $[2, 3]$.

在第一个测试用例中，若 Alex 抽到牌 $2$（他打出该牌，Boris 无法回应），则 Alex 获胜；若 Alex 抽到牌 $1$，则游戏以平局结束。

在第二个测试用例中：

• 若 Alex 抽到牌组 $[3, 4]$、$[2, 4]$ 或 $[1, 4]$，则 Alex 获胜；
• 若 Alex 抽到牌组 $[1, 2]$ 或 $[1, 3]$，则 Boris 获胜；
• 若 Alex 抽到牌组 $[2, 3]$，则游戏以平局结束。