C. Card Game

Consider a game with nn cards (nn is even). Each card has a number written on it, between 11 and nn. All numbers on the cards are different. We say that a card with number xx is stronger than a card with number yy if x>yx>y.

Two players, Alex and Boris, play this game. In the beginning, each of them receives exactly n2n2 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=4n=4, Alex receives the cards [2,3][2,3], and Boris receives the cards [1,4][1,4]. Then the game may go as follows:

• if Alex plays the card 22, then Boris has to respond with the card 44. Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is 11; he plays it, and Alex responds with the card 33. So, the game ends in a draw;
• if Alex plays the card 33, then Boris has to respond with the card 44. Then, Alex's turn ends, and Boris' turn starts. Boris has only one card left, which is 11; he plays it, and Alex responds with the card 22. So, the game ends in a draw.

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

Input

The first line contains one integer tt (1≤t≤301≤t≤30) — the number of test cases.

Then, tt lines follow. The ii-th line contains one even integer nn (2≤n≤602≤n≤60).

Output

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 998244353998244353.

Example

input

Copy

5

2

4

6

8

60

output

Copy

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

思路分析：

如果我们的先手拿到了最大的牌，毫无疑问，游戏结束了，总情况数是在n-1张牌数中后手拿到（n/2）张牌

如果我们的先手没有拿到最大的牌，那么第一回合肯定没有结束游戏，这时候换成了原来的后手变成先手，考虑它赢的情况，拿我们总牌数（注意剩余n-2）张牌，跳出里面最大的给现在所谓的先手就是第二回合所谓的先手赢的情况，拿我们的总情况c（n-2，（n-2）/2）减去它赢的情况和平局情况。

我们上述两种情况相加就是我们的先手赢的情况

设n=2*i

    f[i] = (c[2 * i - 1][i] + (c[2 * i - 2][i - 1] - f[i - 1] - 1 + mod) % mod) % mod;

   这个式子表示先手直接赢的情况，加上后手输的情况

i从1开始递推到n/2就是我们的答案了

#include<iostream>
#include<cstring>
using namespace std;
using LL = long long;
const int maxn = 200, mod = 998244353;
int c[maxn][maxn];
int f[maxn];
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	for(int i = 0; i < maxn; i++)
		for(int j = 0; j <= i; j++)
			if (!j) c[i][j] = 1;
			else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;//预处理出来从i个里面跳出来j个的组合数
	f[1] = 1;
	for(int i = 2; i <= 30; i++)//预处理出来先手获胜的情况
		f[i] = (c[2 * i - 1][i] + (c[2 * i - 2][i - 1] - f[i - 1] - 1 + mod) % mod) % mod;
			//先手拿最大，后手一共拿这么多牌++++      后手（第二轮的先手）先拿牌，最大的，减去总牌数为2*（i-1）先手赢和平局的次数
	int T;
	cin >> T;
	while(T--) {
		int n;
		cin >> n;
		n /= 2;
		cout<<f[n]<<' '<<(c[2 * n][n]-f[n]-1+mod)%mod<<' '<<1<<'\n';
	}
}