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


-----Input-----

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$).


-----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 $998244353$.


-----Examples-----

Input
5
2
4
6
8
60
Output
1 0 1
3 2 1
12 7 1
42 27 1
341102826 248150916 1


-----Note-----

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]$.

Source: codeforces | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Game theory

Constructive algorithms


Solutions:
import math

def nChooseK(n, k):
	return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
soln = {2: [1, 0, 1]}
for n in range(4, 62, 2):
	a = int(nChooseK(n, n // 2)) // 2 % 998244353
	b = int(nChooseK(n - 2, n // 2 - 2)) % 998244353
	a += soln[n - 2][1]
	b += soln[n - 2][0]
	a = a % 998244353
	b = b % 998244353
	soln[n] = [a, b, 1]
import sys
arr = []
for line in sys.stdin:
	arr.append(int(line))
tc = arr[0]
for n in arr[1:]:
	print(*soln[n])


import sys
sys.setrecursionlimit(1000000)

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
from math import comb
ans = [(1, 0, 1), (3, 2, 1), (12, 7, 1), (42, 27, 1)]
p = 998244353
for i in range(10, 61, 2):
	curr = list(ans[-1])
	new = ((ncr(i - 1, i // 2, p) + curr[1]) % p, (ncr(i, i // 2, p) - (ncr(i - 1, i // 2, p) + curr[1]) - 1) % p, 1)
	ans.append(new)
for T in range(int(input())):
	n = ni()
	print(*ans[n // 2 - 1])


from math import comb
from functools import lru_cache
t = int(input())

@lru_cache
def res(n):
	if n == 2:
		return [1, 0]
	else:
		result = [comb(n - 1, n // 2) + res(n - 2)[1], comb(n - 2, n // 2) + res(n - 2)[0]]
		return result
for i in range(t):
	n = int(input())
	print(str(res(n)[0] % 998244353) + ' ' + str(res(n)[1] % 998244353) + ' ' + '1')


import math
p = 998244353
a = [(1, 0)]
for i in range(1, 31):
	b = (math.comb(2 * i, i) // 2 + a[i - 1][1]) % p
	a += [(b % p, (math.comb(2 * i, i) - b - 1) % p)]
for i in range(int(input())):
	print(*a[int(input()) // 2], 1)


t = int(input())
dp = [[0, 1], [0, 0]]

def ncr(n, r):
	ans = 1
	for j in range(1, n + 1):
		ans *= j
	for j in range(1, r + 1):
		ans //= j
	for j in range(1, n - r + 1):
		ans //= j
	return ans
for i in range(2, 31):
	dp[0].append(int(dp[1][i - 1] + ncr(2 * i - 1, i)) % 998244353)
	dp[1].append(int(dp[0][i - 1] + ncr(2 * i - 2, i)) % 998244353)
while t > 0:
	t -= 1
	nn = int(input())
	print(int(dp[0][nn // 2]), int(dp[1][nn // 2]), '1')


def f(n):
	res = 1
	for i in range(2, n + 1):
		res *= i
	return res

def c(n, k):
	return f(n) // f(k) // f(n - k)
l = [0] * 61
for i in range(61):
	l[i] = [0] * 3
(l[2][0], l[2][1], l[2][2]) = (1, 0, 1)
for i in range(4, 61, 2):
	l[i][0] = c(i - 1, i // 2 - 1) + l[i - 2][1]
	l[i][1] = c(i, i // 2) - l[i][0] - 1
	l[i][2] = 1
t = int(input())
for i in range(t):
	n = int(input())
	print(l[n][0] % 998244353, l[n][1] % 998244353, l[n][2] % 998244353)


import sys
input = sys.stdin.readline
import math
MOD = 998244353
dp = [[0, 0, 0] for _ in range(61)]
dp[2][0] = 1
dp[2][1] = 0
dp[2][2] = 1
for i in range(4, 61, 2):
	dp[i][2] = 1
	dp[i][0] = (math.comb(i, i // 2) // 2 + dp[i - 2][1]) % MOD
	dp[i][1] = (math.comb(i, i // 2) - dp[i][0] - dp[i][1] - 1) % MOD
for _ in range(int(input())):
	n = int(input())
	print(dp[n][0], dp[n][1], dp[n][2])


import math
mod = 998244353
for _ in range(int(input())):
	T = int(input())
	r = 0
	(t, u) = (T - 2, T // 2)
	while t > 0:
		r += math.comb(t, u)
		r %= mod
		t -= 4
		u -= 2
	(t, u) = (T - 3, T // 2 - 1)
	while t > 0:
		r += math.comb(t, u)
		r %= mod
		t -= 4
		u -= 2
	tot = math.comb(T, T // 2) % mod
	print((tot - 1 - r + mod) % mod, r, 1)


MAX_N = 60
MOD = 998244353
f = [0] * (MAX_N + 1)
f[0] = 1
for i in range(1, MAX_N + 1):
	f[i] = f[i - 1] * i % MOD
inv_f = [0] * (MAX_N + 1)
inv_f[MAX_N] = pow(f[MAX_N], MOD - 2, MOD)
for i in range(MAX_N, 0, -1):
	inv_f[i - 1] = inv_f[i] * i % MOD

def comb(a, b):
	if a < b:
		return 0
	return f[a] * inv_f[a - b] * inv_f[b] % MOD
t = int(input())
for _ in range(t):
	n = int(input())
	k = n // 2
	w = 0
	for i in range(k, 0, -1):
		w = (w + comb(2 * i - 1 - (k - i) % 2, i)) % MOD
	print(w, (comb(2 * k, k) - w - 1) % MOD, 1)


from math import factorial as f
a = [1]
b = [0]
for i in range(30):
	a.append(f(2 * (i + 2) - 1) // (f(i + 2) * f(i + 1)) + b[-1])
	b.append(f(2 * (i + 2)) // f(i + 2) ** 2 - 1 - a[-1])
for z in range(int(input())):
	n = int(input())
	print(a[n // 2 - 1] % 998244353, b[n // 2 - 1] % 998244353, 1)


from math import comb

def foo(N):
	modulo = 998244353
	d = {2: (1, 0, 1)}
	for n in range(4, N + 1, 2):
		(plose, pwin, pdraw) = d[n - 2]
		k = n // 2
		win = (comb(n - 1, k - 1) + pwin) % modulo
		lose = (comb(n - 2, k) + plose) % modulo
		draw = pdraw
		d[n] = (win, lose, draw)
	return d
t = int(input())
ns = []
for _ in range(t):
	n = int(input())
	ns.append(n)
nmax = max(ns)
d = foo(nmax)
for n in ns:
	(win, lose, draw) = d[n]
	print(win, lose, draw)


T = int(input())
P = 998244353

def fac(n):
	res = 1
	for i in range(1, n + 1):
		res *= i
		res %= P
	return res

def invmod(n):
	return pow(n, P - 2, P)

def nCr(n, r):
	return fac(n) * invmod(fac(r)) * invmod(fac(n - r)) % P
dp = [0] * 62
dp[2] = (1, 0)
for i in range(4, 60 + 1, 2):
	A = (nCr(i - 1, i // 2 - 1) + dp[i - 2][1]) % P
	total = nCr(i, i // 2)
	B = (total - 1 - A + P) % P
	dp[i] = (A, B)

def solve():
	N = int(input())
	print(dp[N][0], dp[N][1], 1, sep=' ')
for _ in range(T):
	solve()


a = [0, 0, 1]
b = [0, 0, 0]
n: int
m: int

def C(n, m):
	if m < n - m:
		m = n - m
	ans = 1
	for i in range(m + 1, n + 1):
		ans *= i
	for i in range(1, n - m + 1):
		ans //= i
	return ans
for i in range(1, 60):
	a += [0]
	b += [0]
i: int
for i in range(4, 61, 2):
	a[i] = C(i - 1, i // 2 - 1) + b[i - 2]
	b[i] = C(i, i // 2) - a[i] - 1
t = int(input())
for exi in range(0, t):
	x = int(input())
	print(a[x] % 998244353, b[x] % 998244353, 1)


from math import comb
for t in range(int(input())):
	d = 998244353
	n = int(input())
	w = [1]
	l = [0]
	for i in range(2, n + 1, 2):
		w.append(comb(i, i // 2) // 2 + l[-1])
		l.append(comb(i, i // 2) - w[-1] - 1)
	print(w[-1] % d, l[-1] % d, 1)


a = [(1, 0, 1), (3, 2, 1), (12, 7, 1), (42, 27, 1), (153, 98, 1), (560, 363, 1), (2079, 1352, 1), (7787, 5082, 1), (29392, 19227, 1), (111605, 73150, 1), (425866, 279565, 1), (1631643, 1072512, 1), (6272812, 4127787, 1), (24186087, 15930512, 1), (93489272, 61628247, 1), (362168442, 238911947, 1), (407470704, 927891162, 1), (474237047, 614943428, 1), (319176974, 87534470, 1), (131938523, 955113935, 1), (558075845, 644336680, 1), (544270478, 253841470, 1), (209493498, 700054910, 1), (859106804, 457241336, 1), (921005664, 6522991, 1), (366933608, 353887625, 1), (142064435, 432533537, 1), (741221694, 874398972, 1), (297907370, 545598131, 1), (341102826, 248150916, 1)]
t = int(input())
for _ in range(t):
	n = int(input()) // 2 - 1
	print(' '.join((str(x) for x in a[n])))


import math
import sys
input = sys.stdin.readline
t = int(input())
modulo = 998244353
win = [0] * 61
loose = [0] * 61
win[2] = 1
loose[2] = 0
for i in range(4, 61, 2):
	total = math.comb(i, i // 2)
	win[i] = math.comb(i - 1, i // 2) + loose[i - 2]
	loose[i] = total - win[i] - 1
for _ in range(t):
	n = int(input())
	print(win[n] % modulo, loose[n] % modulo, 1)


def fact(n):
	res = 1
	for i in range(1, int(n) + 1):
		res = res * i
	return res
t = int(input())
resa = []
resb = []
for i in range(2, 62, 2):
	if i == 2:
		resa.append(1)
		resb.append(0)
		continue
	total = int(fact(i) / (fact(i / 2) * fact(i / 2)))
	resa.append((int(total / 2) + resb[-1]) % 998244353)
	resb.append((total - (int(total / 2) + resb[-1] + 1)) % 998244353)
for i in range(t):
	n = int(input())
	print(resa[int(n / 2) - 1], resb[int(n / 2) - 1], 1)


from math import factorial

def CmbinationNumber(n, m):
	if m <= n:
		a = factorial(n) // (factorial(n - m) * factorial(m))
	return a
a = [0] * 100
a[1] = 1
a[2] = 3
c = [0] * 100
for i in range(3, 31):
	a[i] = CmbinationNumber(2 * i - 1, i - 1) + CmbinationNumber(2 * i - 4, i - 3) + a[i - 2]
for i in range(1, 61):
	c[i] = CmbinationNumber(2 * i, i)
t = int(input())
while t > 0:
	k = int(input())
	k = k // 2
	print('%d %d %d' % (a[k] % 998244353, (c[k] - a[k] - 1) % 998244353, 1))
	t -= 1


mod = 998244353
a = [0] * 200
b = [0] * 200
fac = [0] * 200
fac[1] = 1
for i in range(2, 160):
	fac[i] = i * fac[i - 1]
a[1] = 1
b[1] = 0
a[2] = 3
b[2] = 2
for i in range(3, 70):
	a[i] = fac[2 * i - 1] // (fac[i] * fac[i - 1]) + b[i - 1]
	b[i] = fac[2 * i] // (fac[i] * fac[i]) - a[i] - 1
for _ in range(int(input())):
	n = int(input())
	n //= 2
	print(int(a[n] % mod), int(b[n] % mod), 1)


from math import comb
res = [(0, 0), (1, 0)]
mod = 998244353
for k in range(2, 31):
	a = comb(2 * k - 1, k - 1)
	a += res[k - 1][1]
	b = comb(2 * k, k) - 1 - a
	res.append((a, b))
t = int(input())
for i in range(t):
	n = int(input()) // 2
	print(res[n][0] % mod, res[n][1] % mod, 1)


from math import comb
mod = 998244353
dp = [[0, 0, 0] for _ in range(31)]
for i in range(1, 31):
	dp[i][0] = comb(2 * i, i) // 2 + dp[i - 1][1]
	dp[i][2] = 1
	dp[i][1] = comb(2 * i, i) - dp[i][0] - dp[i][2]
for i in range(int(input())):
	n = int(input())
	print(dp[n // 2][0] % mod, dp[n // 2][1] % mod, dp[n // 2][2] % mod)


def factoriel(n):
	if n == 1:
		return 1
	return n * factoriel(n - 1)
alex = []
boris = []
alex += [1]
boris += [0]
for i in range(1, 30):
	a = factoriel(2 * i + 1) * (i + 1)
	b = factoriel(i + 1) ** 2
	c = int(a / b)
	alex += [c + boris[i - 1]]
	boris += [int(factoriel((i + 1) * 2) / factoriel(i + 1) ** 2) - 1 - alex[i]]
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	print(alex[int(n / 2 - 1)] % 998244353, (int(factoriel(n) / factoriel(int(n / 2)) ** 2) - 1 - alex[int(n / 2 - 1)]) % 998244353, '1')


def f(n, r):
	up = 1
	down = 1
	temp = n - r
	for i in range(1, n + 1):
		up = up * i
	for i in range(1, r + 1):
		down = down * i
	for i in range(1, temp + 1):
		down = down * i
	if down == 0:
		return -1
	else:
		return int(up / down)
mod = 998244353
t = int(input())
a = {}
b = {}
a[2] = 1
b[2] = 0
for i in range(4, 61, 2):
	total = f(i, int(i / 2))
	a[i] = f(i - 1, int(i / 2) - 1) + b[i - 2]
	b[i] = total - a[i] - 1
for i in range(t):
	n = int(input())
	print(a[n] % mod, b[n] % mod, 1)


import math

def ncr(n, r):
	n = int(n)
	r = int(r)
	return math.factorial(n) // math.factorial(r) // math.factorial(n - r)
t = int(input())
for i in range(t):
	M = 998244353
	n = int(input())
	dp = [0] * 71
	dp[2] = 1
	dp[4] = 3
	for j in range(6, 71, 2):
		dp[j] = dp[j - 4]
		dp[j] += ncr(j - 1, j / 2)
		dp[j] += ncr(j - 4, j / 2 - 1)
	ans1 = dp[n]
	ans2 = ncr(n, n / 2) - ans1 - 1
	ans1 %= M
	ans2 %= M
	print(ans1, ans2, 1)


from math import factorial

def choose(n, k):
	return factorial(n) // factorial(k) // factorial(n - k)

def calc(n):
	if n == 2:
		return [1, 0, 1]
	else:
		a = calc(n - 2)
		return [choose(n - 1, n // 2) + a[1], choose(n - 2, n // 2) + a[0], 1]
t = int(input())
for i in range(t):
	mod = 998244353
	n = int(input())
	a = calc(n)
	a = list(map(lambda x: x % mod, a))
	print(*a)


dp1 = []
dp2 = []
mod = 998244353

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
for i in range(0, 62, 1):
	dp1.insert(i, 0)
	dp2.insert(i, 0)
dp1[2] = 1
for i in range(4, 62, 2):
	toadd = ncr(i - 1, int(i / 2), mod)
	total = ncr(i, int(i / 2), mod)
	dp1[i] = ((dp2[i - 2] + mod) % mod + toadd % mod) % mod
	dp2[i] = total - dp1[i] - 1
t = int(input())
while t:
	n = int(input())
	print(dp1[n], (dp2[n] + mod) % mod, 1, sep=' ', end='\n')
	t = t - 1


import math
A = [1]
B = [0]
for n in range(4, 62, 2):
	A.append((B[-1] + math.comb(n - 1, n // 2 - 1)) % 998244353)
	B.append((math.comb(n, n // 2) - A[-1] - 1) % 998244353)
t = int(input())
for _ in range(t):
	n = int(input())
	ind = n // 2 - 1
	print(str(A[ind]) + ' ' + str(B[ind]) + ' ' + '1')


from math import comb
(res, M) = ([[1, 0, 1]], 998244353)
for i in range(4, 61, 2):
	half = comb(i, i >> 1) // 2 % M
	res += ([(half + res[-1][1]) % M, (half - res[-1][1] - 1) % M, 1],)
for _ in range(int(input())):
	print(*res[int(input()) // 2 - 1])


from math import comb
MOD = 998244353
wins = [0] * 61
loses = [0] * 61
for n in range(2, 61, 2):
	wins[n] = loses[n - 2] + comb(n - 1, n // 2)
	loses[n] = wins[n - 2] + comb(n - 2, n // 2)
	wins[n] %= MOD
	loses[n] %= MOD
for _ in range(int(input())):
	n = int(input())
	print(wins[n], loses[n], 1)


import sys
import math

def solve(n, m):
	if n == 2:
		m[2] = (1, 0, 1)
		return (1, 0, 1)
	num_a_wins = 0
	num_b_wins = 0
	num_draws = 0
	num_a_wins += math.comb(n - 1, n // 2 - 1)
	if n - 2 in m:
		(b, a, d) = m[n - 2]
	else:
		(b, a, d) = solve(n - 2, m)
	num_a_wins += a
	num_b_wins += b
	num_draws += d
	num_b_wins += math.comb(n - 2, n // 2 - 2)
	m[n] = (num_a_wins, num_b_wins, num_draws)
	return (num_a_wins, num_b_wins, num_draws)
t = int(sys.stdin.readline())
MOD = 998244353
m = {}
for i in range(t):
	n = int(sys.stdin.readline())
	(a, b, d) = solve(n, m)
	print(a % MOD, b % MOD, d % MOD)


import math
p = 998244353
a = [1]
b = [0]
for k in range(1, 31):
	a_k = a[k - 1]
	b_k = b[k - 1]
	a_k1 = b_k + math.comb(2 * k + 1, k + 1) % p
	b_k1 = a_k + math.comb(2 * k, k + 1) % p
	a.append(a_k1)
	b.append(b_k1)
for i in range(int(input())):
	n = int(input())
	print(a[n // 2 - 1] % p, b[n // 2 - 1] % p, 1)


card_game = {2: '1 0 1', 4: '3 2 1', 6: '12 7 1', 8: '42 27 1', 10: '153 98 1', 12: '560 363 1', 14: '2079 1352 1', 16: '7787 5082 1', 18: '29392 19227 1', 20: '111605 73150 1', 22: '425866 279565 1', 24: '1631643 1072512 1', 26: '6272812 4127787 1', 28: '24186087 15930512 1', 30: '93489272 61628247 1', 32: '362168442 238911947 1', 34: '407470704 927891162 1', 36: '474237047 614943428 1', 38: '319176974 87534470 1', 40: '131938523 955113935 1', 42: '558075845 644336680 1', 44: '544270478 253841470 1', 46: '209493498 700054910 1', 48: '859106804 457241336 1', 50: '921005664 6522991 1', 52: '366933608 353887625 1', 54: '142064435 432533537 1', 56: '741221694 874398972 1', 58: '297907370 545598131 1', 60: '341102826 248150916 1'}
t = int(input())
for i in range(t):
	cards = int(input())
	print(card_game[cards])


from math import comb
p = 998244353
f = lambda x: comb(x * 2, x) // 2 % p
a = [(0, 0), (1, 0)]
for i in range(2, 31):
	a += [((f(i) + a[-1][1]) % p, (f(i) - a[-1][1] - 1 + p) % p)]
for _ in range(int(input())):
	n = int(input()) // 2
	print(*a[n], 1)


hsh = {}

def fact(n):
	if n == 0 or n == 1:
		return 1
	if n in hsh:
		return hsh[n]
	hsh[n] = n * fact(n - 1)
	return hsh[n]

def comp(n, r):
	p = fact(n)
	m = fact(r) * fact(n - r)
	return p // m
hsh2 = {}

def solve(n, flag):
	if n == 2:
		return flag
	if n in hsh2:
		return hsh2[n] if flag else comp(n, n / 2) - 1 - hsh2[n]
	cur = comp(n - 1, n / 2 - 1)
	cur += solve(n - 2, 0)
	hsh2[n] = cur
	if flag:
		return hsh2[n]
	return comp(n, n / 2) - cur - 1
mod = 998244353
t = int(input())
while t > 0:
	n = int(input())
	print(int(solve(n, 1) % mod), ' ', int(solve(n, 0) % mod), ' ', 1)
	t -= 1


import math
p = 998244353
X = [(1, 0)]
for i in range(1, 31):
	Y = (math.comb(2 * i, i) // 2 + X[i - 1][1]) % p
	X += [(Y % p, (math.comb(2 * i, i) - Y - 1) % p)]
for i in range(int(input())):
	print(*X[int(input()) // 2], 1)


import math

def a(n):
	return math.comb(n, n // 2) - b(n) - 1

def b(n):
	if n == 2:
		return 0
	elif n == 4:
		return 2
	else:
		return math.comb(n - 2, n // 2 - 2) + a(n - 2)
for i in range(int(input())):
	n = int(input())
	if n > 4:
		B = b(n)
		A = a(n)
		print(A % 998244353, B % 998244353, 1)
	elif n == 2:
		print(1, 0, 1)
	else:
		print(3, 2, 1)


from math import comb
mod = 998244353

def solve(n):
	alex = [0] * (n + 1)
	boris = [0] * (n + 1)
	for i in range(2, n + 1, 2):
		t = comb(i, i // 2)
		alex[i] = boris[i - 2] + t // 2
		boris[i] = t - alex[i] - 1
		alex[i] %= mod
		boris[i] %= mod
	return [alex[n], boris[n], 1]

def main():
	for _ in range(int(input())):
		n = int(input())
		print(' '.join([str(e) for e in solve(n)]))
main()


from math import comb
l = [[0] * 2 for i in range(61)]
for i in range(1, 31):
	l[i * 2][0] = comb(i * 2 - 1, i - 1) + l[i * 2 - 2][1]
	l[i * 2][1] = comb(i * 2, i) - l[i * 2][0] - 1
for i in range(int(input())):
	print(*map(lambda x: x % 998244353, l[int(input())]), 1)


t = int(input())

def ncr(n, r):
	if r == 0:
		return 1
	ans = 1
	for i in range(1, r + 1):
		ans = ans * (n - i + 1) // i
	return ans

def fn(n):
	if n <= 4:
		return n - 1
	else:
		return ncr(n - 1, n // 2) + ncr(n - 4, n // 2 - 1) + fn(n - 4)
for t1 in range(t):
	n = int(input())
	alex = fn(n)
	tot = ncr(n, n // 2)
	print(alex % 998244353, (tot - alex - 1) % 998244353, 1)


NMAX = 61
MOD = 998244353
cnks = [[0 for _ in range(NMAX)] for __ in range(NMAX)]
for i in range(NMAX):
	cnks[i][0] = 1
	cnks[i][i] = 1
for i in range(2, NMAX):
	for j in range(1, i):
		cnks[i][j] = (cnks[i - 1][j] + cnks[i - 1][j - 1]) % MOD
fs = [0 for _ in range(NMAX)]
fs[2] = 1
for k in range(4, NMAX, 2):
	fs[k] = (cnks[k - 1][(k - 1) // 2] + cnks[k - 2][k // 2 - 1] - fs[k - 2] - 1) % MOD
t = int(input())
for _ in range(t):
	n = int(input())
	print(f'{fs[n]} {(cnks[n][n // 2] - fs[n] - 1) % MOD} 1')


import math
t = int(input())
ans = [[1, 0]]
for i in range(2, 31, 1):
	n = 2 * i
	x = ans[i - 2][0]
	y = ans[i - 2][1]
	tot = math.comb(n, n // 2)
	val = math.comb(n - 1, n // 2 - 1)
	ans.append([val + y, tot - 1 - val - y])
for t1 in range(t):
	n = int(input())
	i = n // 2 - 1
	print(ans[i][0] % 998244353, ans[i][1] % 998244353, 1)


from math import factorial

def C(n, k):
	return factorial(n) // (factorial(k) * factorial(n - k))

def gam(n):
	res = [0] * 3
	if n == 2:
		return [1, 0, 1]
	w = gam(n - 2)
	res[0] += C(n - 1, n // 2)
	res[1] += C(n - 2, n // 2)
	res[2] += w[2]
	res[0] += w[1]
	res[1] += w[0]
	return res
rez = {}
for i in range(2, 61, 2):
	q = gam(i)
	for x in range(3):
		q[x] = q[x] % 998244353
	rez[i] = q
t = int(input())
for i in range(t):
	n = int(input())
	print(*rez[n])


from math import comb
mod = 998244353

def WDL(n):
	if n == 2:
		return [1, 1, 0]
	wdl = WDL(n - 2)[::-1]
	wdl[0] += comb(n - 1, n // 2)
	wdl[2] += comb(n - 2, n // 2)
	return wdl
t = int(input())
for _ in range(t):
	n = int(input())
	print(WDL(n)[0] % mod, WDL(n)[2] % mod, WDL(n)[1] % mod)


import math
mod = 998244353
for i in range(int(input())):
	a = int(input())
	total = math.comb(a, a // 2)
	alex = 0
	for i in range(a, 0, -4):
		alex += math.comb(i - 1, i // 2 - 1)
		if i > 4:
			alex += math.comb(i - 4, i // 2 - 3)
	print(alex % mod, (total - 1 - alex) % mod, 1)


def c(n):
	ans = 1
	for i in range(n // 2 + 1, n):
		ans *= i
	for i in range(1, n // 2):
		ans //= i
	return ans

def c2(n):
	ans = 1
	for i in range(n // 2 + 1, n + 1):
		ans *= i
	for i in range(1, n // 2 + 1):
		ans //= i
	return ans
t = int(input())
for ti in range(t):
	alex = 0
	boris = 0
	n = int(input())
	for i in range(n // 2):
		alex = boris + c(i * 2 + 2)
		boris = c2(i * 2 + 2) - alex - 1
	print(alex % 998244353, boris % 998244353, '1')


import operator as op
from functools import reduce

def ncr(n, r):
	if n <= 0 or r < 0:
		return 0
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def uno(n):
	if n == 0:
		return 0
	return ncr(n - 1, n // 2 - 1) + dos(n - 2)

def dos(n):
	if n == 0:
		return 0
	return ncr(n - 2, n // 2 - 2) + uno(n - 2)
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = uno(n)
	b = dos(n)
	c = 1
	mod = 998244353
	a %= mod
	b %= mod
	print(a, b, c)


from math import comb
MOD = 998244353

def a(n: int):
	if n == 0:
		return 0
	if n == 2:
		return 1
	return (comb(n - 1, n // 2) + comb(n - 4, n // 2 - 1) + a(n - 4)) % MOD

def b(n: int):
	if n == 0:
		return 0
	if n == 2:
		return 0
	return (comb(n - 3, n // 2 - 1) + comb(n - 2, n // 2) + b(n - 4)) % MOD

def solve():
	n = int(input())
	print(a(n), b(n), 1)
for _ in range(int(input())):
	solve()


answers = [None, [1, 0, 1]]
fact = [1, 1]
for i in range(2, 61):
	fact.append(fact[-1] * i)

def get_nCr(n, r):
	ans = fact[n] // fact[n - r] // fact[r]
	return ans
for i in range(4, 62, 2):
	total = 1
	for j in range(i // 2 + 1, i + 1):
		total *= j
	for j in range(1, i // 2 + 1):
		total //= j
	temp = [total, 0, 1]
	temp[1] += answers[i // 2 - 1][0]
	temp[1] += get_nCr(i - 2, i - 2 - i // 2)
	temp[0] -= temp[1] + temp[2]
	answers.append(temp)
for i in range(1, 31):
	answers[i][0] %= 998244353
	answers[i][1] %= 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	print(*answers[n // 2])


import math

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
ans1 = [1, 3]
ans2 = [0, 2]
MOD = 998244353
for i in range(6, 61, 2):
	s = nCr(i - 1, i // 2) % MOD
	x = ans1[-1]
	ans1.append((s + ans2[-1]) % MOD)
	s = nCr(i - 2, i // 2) % MOD
	ans2.append((s + x) % MOD)
for _ in range(int(input())):
	n = int(input())
	n = n // 2 - 1
	print(ans1[n], ans2[n], 1)


t = int(input())
f = {}

def fact(x):
	if x == 0:
		return 1
	if x not in f:
		s = fact(x - 1) * x
		f[x] = s
		return s
	else:
		return f[x]
ff = {}

def c(N, K):
	return fact(N) // (fact(K) * fact(N - K))

def fin(n):
	if n == 2:
		return [1, 0]
	else:
		if n not in ff:
			a = c(n - 1, n // 2 - 1)
			a += fin(n - 2)[1]
			b = c(n, n // 2) - a - 1
			ff[n] = [a % mod, b % mod]
		return ff[n]
for _ in range(t):
	n = int(input())
	mod = 998244353
	print(fin(n)[0] % mod, fin(n)[1] % mod, 1)


t = int(input())
mod = 998244353

def binomialCoeffUtil(n, k, dp):
	for i in range(n + 1):
		for j in range(min(i, k) + 1):
			if j == 0 or j == i:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
	return dp[n][k]
dp = [[-1 for y in range(61 + 1)] for x in range(61 + 1)]
binomialCoeffUtil(61, 61, dp)
ans = 61 * [0]

def solve():
	n = int(input())
	print((mod + dp[n][n // 2] - ans[n] - 1) % mod, ans[n], 1)
for i in range(t):
	for i in range(2, 61, 2):
		ans[i] = (mod + dp[i][i // 2] - (ans[i - 2] + dp[i - 1][i // 2 - 1]) - 1) % mod
	solve()


from math import factorial as fact
MOD = 998244353
b = [None] * 61
f = [None] * 61
b[2] = 0
f[2] = 2
for i in range(4, 61, 2):
	f[i] = fact(i) // fact(i // 2) ** 2
	b[i] = f[i] // 2 - b[i - 2] - 1
t = int(input())
for _ in range(t):
	i = int(input())
	print(*map(lambda x: x % MOD, (f[i] - b[i] - 1, b[i], 1)))


from math import comb, factorial
awin = [0 for _ in range(100)]
bwin = [0 for _ in range(100)]
awin[2] = 1
bwin[2] = 0
MOD = 998244353
for i in range(4, 61, 2):
	awin[i] = (bwin[i - 2] + comb(i - 1, i // 2 - 1)) % MOD
	bwin[i] = (comb(i, i // 2) - 1 - awin[i]) % MOD
TC = int(input())
for _ in range(TC):
	N = int(input())
	print(awin[N], bwin[N], 1)


import math as m
a = [[0, 0]] * 70
a[2] = [1, 0]
for i in range(4, 66, 2):
	a[i] = [(m.comb(i - 1, i // 2 - 1) + a[i - 2][1]) % 998244353, (m.comb(i, i // 2) - (m.comb(i - 1, i // 2 - 1) + a[i - 2][1] + 1)) % 998244353]
for _ in range(int(input())):
	n = int(input())
	print(str(a[n][0]) + ' ' + str(a[n][1]) + ' 1')


from math import factorial as f

def res(n):
	if n == 2:
		return (1, 0, 1)
	(a, b, c) = res(n - 2)
	return ((f(n) * pow(f(n // 2), -2, 998244353) * pow(2, -1, 998244353) + b) % 998244353, (f(n - 2) * pow(f(n // 2 - 2), -1, 998244353) * pow(f(n // 2), -1, 998244353) + a) % 998244353, 1)
for _ in range(int(input())):
	n = int(input())
	print(*res(n))


c = [[1] * 61 for i in range(61)]
for i in range(61):
	for j in range(61):
		if j > i:
			c[j][i] = 0
for i in range(1, 61):
	for j in range(1, i + 1):
		c[j][i] = (c[j][i - 1] + c[j - 1][i - 1]) % 998244353
f = [0] * 61
f[2] = 1
f[4] = 3
for i in range(6, 61, 2):
	f[i] = f[i - 4] + c[int(i / 2) - 1][i - 1] + c[int(i / 2) - 3][i - 4]
	f[i] %= 998244353
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	x = f[n]
	y = (c[int(n / 2)][n] - f[n] - 1 + 998244353) % 998244353
	print(f'{x} {y} 1')


mod = 998244353

def C(n, r):
	ans = 1
	for i in range(1, r + 1):
		ans = ans * n * pow(i, -1, mod)
		n -= 1
	return (ans + 5 * mod) % mod
l = [[1, 0, 1]]
for i in range(4, 61, 2):
	combi_term = C(i - 1, (i - 1) // 2) % mod
	full = C(i, i // 2) % mod
	a = (combi_term + l[-1][1]) % mod
	b = (full - a - 1 + mod) % mod
	c = 1
	l.append([a, b, c])
for _ in range(int(input())):
	n = int(input()) - 1
	t = l[n // 2]
	print(t[0], t[1], t[2])


import math
ntestcases = int(input())
for i in range(ntestcases):
	n = int(input())

	def GoesFirstWins(k):
		if k == 2:
			return 1
		return math.comb(k - 1, k // 2 - 1) + GoesSecondWins(k - 2)

	def GoesSecondWins(k):
		if k == 2:
			return 0
		return math.comb(k, k // 2) - GoesFirstWins(k) - 1
	alexWins = GoesFirstWins(n) % 998244353
	borisWins = (math.comb(n, n // 2) - alexWins - 1) % 998244353
	print(' '.join(list(map(str, [alexWins, borisWins, '1']))))


from collections import deque, defaultdict, Counter
from math import *
from heapq import *
from functools import cmp_to_key, lru_cache
fact = {}

def factorial(n):
	if n in [0, 1]:
		return 1
	if n in fact:
		return fact[n]
	fact[n] = n * factorial(n - 1)
	return fact[n]
factorial(60)

def ncr(n, r):
	return fact[n] / (fact[n - r] * fact[r])
memo = {2: [1, 0, 1], 4: [3, 2, 1], 6: [12, 7, 1]}

def build(n):
	if n in memo:
		return memo[n]
	prev = int(ncr(n - 1, int(n / 2 - 1)) % 998244353 + build(n - 2)[1] % 998244353)
	memo[n] = [prev, int(ncr(n, n / 2) % 998244353 - prev - 1), 1]
	return memo[n]

class Solution:

	def solve(self):
		n = int(input())
		if n in memo:
			return ' '.join(map(lambda x: str(int(x % 998244353)), memo[n]))
		else:
			return ' '.join(map(lambda x: str(int(x % 998244353)), build(n)))
ob = Solution()
for _ in range(int(input())):
	print(ob.solve())


def fact(x):
	if x == 1:
		return 1
	return x * fact(x - 1)
a = [0] * 61
b = [0] * 61
a[2] = 1
b[2] = 0
a[4] = 3
b[4] = 2
for t in range(5, 61):
	if t % 2 == 0:
		a[t] = b[t - 2] + fact(t - 1) // fact(t // 2 - 1) // fact(t - t // 2)
		b[t] = fact(t) // fact(t // 2) // fact(t // 2) - 1 - a[t]
n = int(input())
for t in range(n):
	x = int(input())
	print(a[x] % 998244353, b[x] % 998244353, 1)