卡牌游戏

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有一个使用 $n$ 张牌的游戏，其中 $n$ 为偶数。每张牌上分别写有 $1$ 到 $n$ 中的一个整数，且所有牌上的数字互不相同。若 $x>y$，则称数字为 $x$ 的牌比数字为 $y$ 的牌更强。

Alex 和 Boris 进行游戏。开始时，每人恰好获得 $\frac n2$ 张牌，每张牌恰好属于一名玩家。随后两人轮流行动，Alex 先手。

一名玩家行动时，必须打出手中的一张牌。如果对手没有更强的牌，对手立即输掉游戏；否则，对手必须打出一张更强的牌作为回应。打出的两张牌都会被移出游戏。若此时双方都没有牌，游戏以平局结束；否则，下一轮由刚才作出回应的玩家先行动。

考虑把全部牌平均分给两人的所有方案。求在双方都采用最优策略时，Alex 获胜、Boris 获胜以及平局的分牌方案数。如果至少有一张牌的归属不同，就视为不同的分牌方案。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

接下来 $t$ 行，每行包含一个偶数 $n$。

输出格式

对每个测试用例输出三个整数，依次表示 Alex 获胜、Boris 获胜以及平局的分牌方案数。答案均对 $998244353$ 取模。

样例输入 1

5
2
4
6
8
60

样例输出 1

1 0 1
3 2 1
12 7 1
42 27 1
341102826 248150916 1

数据范围

对于所有数据，$1\le t\le 30$，$2\le n\le 60$，且 $n$ 为偶数。