Marin wants you to count number of permutations that are beautiful. A beautiful permutation of length $n$ is a permutation that has the following property: $$ \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1, $$ where $\gcd$ is the greatest common divisor .

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3, 4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

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

Each test case consists of one line containing one integer $n$ ($1 \le n \le 10^3$).


-----Output-----

For each test case, print one integer — number of beautiful permutations. Because the answer can be very big, please print the answer modulo $998\,244\,353$.


-----Examples-----

Input
7
1
2
3
4
5
6
1000
Output
0
1
0
4
0
36
665702330


-----Note-----

In first test case, we only have one permutation which is $[1]$ but it is not beautiful because $\gcd(1 \cdot 1) = 1$.

In second test case, we only have one beautiful permutation which is $[2, 1]$ because $\gcd(1 \cdot 2, 2 \cdot 1) = 2$.

Difficulty: EASY
Tags: Number theory

Combinatorics

Mathematics

Starter code:

Solutions:
f = [1]
mod = 998244353
for i in range(1, 1001):
	f.append(f[i - 1] * i % mod)

def solve():
	n = int(input())
	if n % 2 == 1:
		return 0
	return f[n // 2] * f[n // 2] % mod
num_test = int(input())
for t in range(num_test):
	print(solve())


M = 998244353
a = [1]
for i in range(1, 501):
	a += (a[-1] * i % M,)
for n in [*map(int, open(0))][1:]:
	print(~n % 2 * a[n // 2] ** 2 % M)


mod = 998244353
fact = [1 for i in range(1001)]
for i in range(2, 1000 + 1):
	fact[i] = i * fact[i - 1] % mod
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	elif not n & 1:
		print(fact[n // 2] ** 2 % mod)
	else:
		print(0)


factorials = [1]
for i in range(1, 501):
	factorials.append(factorials[-1] * i % 998244353)
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(factorials[n // 2] ** 2 % 998244353)


a = int(input())
k = [1]
for i in range(1, 1000):
	k.append(k[-1] * i * i % 998244353)
for i in range(a):
	x = int(input())
	print(0 if x % 2 == 1 else k[x // 2])


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
mod = 998244353
fact = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, 10 ** 3 + 1):
	fact.append(fact[-1] * i % mod)
	inv.append(inv[mod % i] * (mod - mod // i) % mod)
	finv.append(finv[-1] * inv[-1] % mod)
t = int(input())
for _ in [0] * t:
	n = int(input())
	if n % 2:
		print(0)
	else:
		print(fact[n // 2] * fact[n // 2] % mod)


import sys
MOD = 998244353
step = [1, 1, 2]
for i in range(1005):
	step.append(step[-1] * len(step) % MOD)
T = int(sys.stdin.readline().strip())
for t in range(T):
	n = int(sys.stdin.readline().strip())
	if n % 2 == 1:
		print(0)
	else:
		p = n // 2
		ans = step[p] ** 2 % MOD
		print(ans)


mod = 998244353
fac = [1]
for i in range(1, 1010):
	fac.append(fac[-1] * i % mod)
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(pow(fac[n // 2], 2, mod))


import math
t = int(input())
fact = [0 for i in range(1001)]
fact[0] = 1
for i in range(1, 1001):
	fact[i] = i * fact[i - 1] % 998244353
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		print(fact[n // 2] * fact[n // 2] % 998244353)
	else:
		print(0)


t = int(input())
pre = [0] * 1010
pre[2] = 1
step = 2
MOD = 998244353
for i in range(4, 1009, 2):
	pre[i] = pre[i - 2] * step % MOD * step % MOD
	step += 1
for _ in range(t):
	n = int(input())
	print(pre[n] % MOD)


a = [1] * 1003
a[1] = 1
x = 998244353
for i in range(2, 1000):
	a[i] = a[i - 1] * i % x
for t in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(a[n // 2] ** 2 % x)


l = [0, 0, 1, 0, 4]
for i in range(5, 1002):
	if i % 2 == 1:
		l.append(0)
	else:
		l.append(l[-2] % 998244353 * (i / 2) * (i / 2) % 998244353)
for _ in range(int(input())):
	n = int(input())
	print(int(l[n]))


def fac_iter():
	n = 1
	yield n
	for p in range(1, 1001):
		n = n * p % 998244353
		yield n
fac = [v for v in fac_iter()]
for _ in range(int(input())):
	n = int(input())
	if n & 1:
		print(0)
	else:
		n >>= 1
		print(fac[n] * fac[n] % 998244353)


l = list(map(lambda a: a, [0] * 1001))
l[0] = 1
for i in range(1, 1001):
	l[i] = l[i - 1] * i % 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		ans = l[int(n / 2)] ** 2 % 998244353
		print(ans)


MOD = 998244353
fact = [0] * 1010
fact[0] = 1
for i in range(1, 1010):
	fact[i] = fact[i - 1] * i % MOD
for _ in range(int(input())):
	n = int(input())
	if n & 1:
		print(0)
	else:
		print(fact[n // 2] * fact[n // 2] % MOD)


def main():
	f: list = [1]
	for i in range(1, 501):
		f.append(f[-1] * i % 998244353)
	res = []
	t = int(input())
	for _ in range(t):
		i = int(input())
		if i % 2 == 1:
			res.append(0)
		else:
			res.append(f[i // 2] ** 2 % 998244353)
	print('\n'.join(map(str, res)))
main()


mod = 998244353
map = [0] * 1001
map[0] = 1
for i in range(1, 1001):
	map[i] = map[i - 1] * i % mod
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		print(map[n // 2] ** 2 % mod)
	else:
		print(0)


m = 998244353
factorials = [1]
fact = 1
for i in range(1, 501):
	fact = fact * i % m
	factorials.append(fact)

def f(n):
	if n % 2 == 1:
		return 0
	answer = factorials[n // 2] * factorials[n // 2] % m
	return answer
for i in range(int(input())):
	n = int(input())
	print(f(n))


import sys
import math
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def main():
	mod = 998244353
	fact = [1]
	ml = 1
	for i in range(1, 1001):
		ml = ml % mod * i % mod % mod
		fact.append(ml)
	for t in range(get_int()):
		n = int(input())
		if n % 2:
			print(0)
			continue
		tp = n // 2
		res = fact[tp] * fact[tp] % mod
		print(res)
main()


t = int(input())
mod = 998244353
f = []
f.append(1)
for i in range(1, 1000 + 1):
	val = f[i - 1] * i % mod
	f.append(int(val))
for _ in range(t):
	n = int(input())
	ans = 0
	if n % 2 == 1:
		ans = 0
	else:
		n = int(n / 2)
		ans = f[n] * f[n] % mod
	print(ans)


from itertools import permutations
N = int(1000.0)
MOD = 998244353
fact = [1]
for i in range(1, N + 1):
	fact.append(i * fact[-1] % MOD)
T = int(input())
for tc in range(1, 1 + T):
	n = int(input())
	count = 0 if n % 2 else fact[n // 2] * fact[n // 2 - 1] * n // 2 % MOD
	print(count)


from functools import lru_cache
MOD = 998244353

@lru_cache(maxsize=None)
def fact(n):
	if n == 0:
		return 1
	return n % MOD * fact(n - 1) % MOD
for _ in range(int(input())):
	n = int(input())
	if n % 2:
		print(0)
	else:
		print(fact(n // 2) * fact(n // 2) % MOD)


facts = [1]
p = 998244353
for i in range(1, 1001):
	facts.append(i * facts[i - 1] % p)
for _ in range(int(input())):
	n = int(input())
	if n % 2:
		print(0)
		continue
	print(facts[n // 2] ** 2 % p)


from collections import Counter, defaultdict, deque, namedtuple
from functools import lru_cache
from typing import List, Dict
import bisect as b
import heapq as h
import math as m
MOD = 998244353

def inti():
	return int(input())

def ints():
	return [int(x) for x in input().split()]

def main_tc(factorial):
	n = inti()
	if n % 2 == 1:
		print(0)
		return
	answer = factorial[n // 2] * factorial[n // 2]
	answer %= MOD
	print(answer)

def main():
	factorial = [None] * 1001
	factorial[0] = 1
	for i in range(1, 1001):
		factorial[i] = factorial[i - 1] * i
		factorial[i] %= MOD
	tc = inti()
	for _ in range(tc):
		main_tc(factorial)
main()


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(0)
		continue
	ans = math.factorial(n // 2) % 998244353
	print(ans * ans % 998244353)


def main():
	t = int(input())
	res = []
	factorial = [1]
	for i in range(2, 1001):
		factorial.append(factorial[-1] * i)
	for i in range(1, 1001):
		if i % 2 == 1:
			res.append(0)
		else:
			res.append(factorial[i // 2 - 1] ** 2 % 998244353)
	for p in range(t):
		n = int(input())
		print(res[n - 1])
main()


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		mod = 998244353
		k = math.factorial(n // 2) % mod
		print(k * k % mod)


mod = 998244353
fac = [1]
for i in range(1000):
	fac.append(fac[i] * (i + 1) % mod)
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 != 0:
		print(0)
	else:
		print(fac[n // 2] ** 2 % mod)


import functools

class F:

	def __init__(self, max_n):
		self.cache = [1] * (max_n + 1)
		for i in range(1, max_n + 1):
			self.cache[i] = self.cache[i - 1] * i

	def __call__(self, n):
		return self.cache[n]
f = F(1000)

def main():
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(pow(f(n // 2), 2, 998244353))
t = int(input())
for _ in range(t):
	main()


mod = 998244353
dp = [1] * 501
for i in range(1, 501):
	dp[i] = i * dp[i - 1] % mod
for _ in range(int(input())):
	n = int(input())
	if n & 1:
		print(0)
	else:
		ans = dp[n // 2] * dp[n // 2] % mod
		print(ans)


l = [1]
sas = 1
for s in range(1, 501):
	sas *= s
	l.append(sas)
t = int(input())
for i in range(t):
	a = int(input())
	if a % 2 == 1:
		print('0')
	else:
		print(l[a // 2] ** 2 % 998244353)


from math import factorial
for _ in range(int(input())):
	n = int(input())
	if n % 2:
		print(0)
		continue
	print(pow(factorial(n // 2), 2, 998244353))


import math

def factorial(n):
	return math.factorial(n)
for _ in range(int(input())):
	n = int(input())
	if n & 1:
		print(0)
		continue
	else:
		ans = pow(math.factorial(n // 2), 2, 998244353)
		print(ans)


from math import factorial
t = int(input())
facts = [1]
for i in range(1, 1010):
	facts.append(facts[-1] * i % 998244353)
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		print(facts[n // 2] ** 2 % 998244353)
	else:
		print(0)


import math

def res(n):
	odd = int((n + 1) / 2)
	even = n - odd
	ans = 0
	if odd > even:
		return ans
	else:
		ans = (math.factorial(odd) % 998244353) ** 2 % 998244353
		return ans
t = int(input().strip('\n'))
for i in range(t):
	n = int(input().strip('\n'))
	print(res(n))


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2:
		print(0)
	else:
		mod = 998244353
		x = n // 2
		t = math.factorial(x)
		ans = pow(t, 2, mod)
		print(ans)


t = int(input())
gt = [1]
for i in range(1, 1001):
	gt.append(gt[i - 1] * i)
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		x = gt[n // 2]
		print(x * x % 998244353)


from math import factorial
for jj in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(pow(factorial(n // 2), 2, 998244353))


import math
t = int(input())
m = 998244353
while t:
	t -= 1
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		a = math.factorial(n // 2) % m
		print(a * a % m)


import sys
import math
import itertools
mod = 998244353

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def rls():
	return list(map(str, input().split()))

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

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1
for _ in range(ri()):
	n = ri()
	if n % 2 == 1:
		print(0)
	else:
		ans = math.factorial(n // 2)
		ans = ans % mod * ans % mod % mod
		print(ans)


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
ans = [0, 1]
j = 2
p = 1
for i in range(3, 1001):
	if i % 2 == 0:
		ans.append(p * j ** 2)
		p = ans[-1]
		j += 1
	else:
		ans.append(0)
for t in wtf[1:]:
	n = int(t)
	print(ans[n - 1] % 998244353)


import math
T = int(input())
for t in range(T):
	n = float(input())
	if n % 2 == 1:
		print(0)
	else:
		x = math.factorial(n / 2) % 998244353
		print(x ** 2 % 998244353)


import sys, math
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	if n % 2 == 1:
		print(0)
	else:
		x = n // 2
		y = math.factorial(x)
		print(y * y % 998244353)


a = [1] * 1005
for i in range(1, 1000):
	a[i] = i * a[i - 1]
total = int(input())
cnt = 1
while cnt <= total:
	ans = 0
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(a[int(n / 2)] * a[int(n / 2)] % 998244353)
	cnt += 1


from calendar import c
import sys
import math
T = int(input())
M = 998244353
for _ in range(T):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		a = math.factorial(n // 2) % M
		b = a * a % M
		print(b)


import sys
from collections import defaultdict
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def factorial(n, facts):
	for i in range(1, n):
		facts[i] = i * facts[i - 1]
tc = inp()
facts = [1] * (10 ** 3 + 1)
factorial(10 ** 3, facts)
while tc:
	n = inp()
	if n % 2 == 1:
		print(0)
	else:
		permutations = facts[n // 2] ** 2 % 998244353
		print(permutations)
	tc -= 1


import math
for i in range(int(input())):
	a = int(input())
	if a % 2 == 1:
		print(0)
	else:
		print(math.factorial(a // 2) ** 2 % 998244353)


iter = int(input())
l = [0] * 501
l[0] = 1
l[1] = 1

def fac(x):
	if l[x] != 0:
		return l[x]
	else:
		p = 1
		for i in range(x - 1, -1, -1):
			if l[i] != 0:
				p = i
				break
		for i in range(p + 1, x + 1):
			l[i] = l[i - 1] * i
		return l[x]
for j in range(iter):
	n = int(input())
	if n % 2 != 0:
		ans = 0
	else:
		ans = fac(n // 2)
		ans = ans * ans
	print(ans % 998244353)


num = [1] * 1005
for i in range(1, 1000):
	num[i] = i * num[i - 1]
tot = int(input())
cont = 1
while cont <= tot:
	aux = 0
	num2 = int(input())
	if num2 % 2 == 1:
		print(0)
	else:
		print(num[int(num2 / 2)] * num[int(num2 / 2)] % 998244353)
	cont += 1


import math
a = int(input())
for i in range(a):
	b = int(input())
	if b % 2 == 0:
		l = int(math.factorial(b / 2)) ** 2 % 998244353
		print(l)
	else:
		print(0)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2:
		print(0)
	else:
		print(math.factorial(n // 2) ** 2 % 998244353)


import math
case = int(input())
for i in range(case):
	n = int(input())
	if n % 2 == 0:
		print(math.factorial(int(n / 2)) ** 2 % 998244353)
	else:
		print(0)


import math
for n in [*map(int, open(0))][1:]:
	print(~n % 2 * math.factorial(n // 2) ** 2 % 998244353)


import math
f = math.factorial
for _ in range(int(input())):
	x = int(input())
	if x % 2 != 0:
		print(0)
	else:
		print(f(x // 2) ** 2 % 998244353)


import math
n = int(input())
for i in range(n):
	s = int(input())
	if s % 2 == 1:
		print(0)
	else:
		print(math.factorial(s // 2) ** 2 % 998244353)


import math
for u in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(0)
	else:
		print(math.factorial(n // 2) ** 2 % 998244353)


from math import factorial
cas = int(input())
f = []
for j in range(cas):
	n = int(input())
	if n % 2 != 0:
		c = 0
	else:
		c = pow(factorial(n // 2), 2) % 998244353
	f.append(c)
for i in range(cas):
	print(f[i])


c = int(input())
import math
for z in range(0, c):
	n = int(input())
	if n % 2 == 0:
		x = math.factorial(n // 2 - 1) ** 2 * (n // 2) * (n // 2)
		print(x % 998244353)
	else:
		print(0)


import math
T = int(input())
for _ in range(T):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(math.factorial(n // 2) ** 2 % 998244353)


from math import factorial as f
import sys
input = lambda : sys.stdin.readline().strip()
m = 998244353
for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(0)
	else:
		print(f(n // 2) ** 2 % m)


import math
n = int(input())
for i in range(n):
	k = int(input())
	if k % 2 != 0:
		print(0)
	else:
		b = math.factorial(k // 2)
		print(int(b * b % 998244353))


from math import factorial
t = int(input())
while t:
	n = int(input())
	if n % 2:
		ans = 0
	else:
		ans = factorial(n // 2) ** 2
	print(ans % 998244353)
	t -= 1


from math import factorial
t = int(input())
for _ in range(t):
	ans = 0
	n = int(input())
	if n % 2 == 1:
		ans = 0
	else:
		ans_ = factorial(n // 2)
		ans += ans_ ** 2
	ans = ans % 998244353
	print(ans)


from math import factorial
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		m = factorial(n // 2) ** 2
		print(m % 998244353)
	else:
		print(0)


import math
tc = int(input())
for i in range(tc):
	x = int(input())
	if x % 2 == 1:
		print(0)
	else:
		f = math.factorial(x // 2)
		print(f ** 2 % 998244353)


import math
k = int(input())
for i in range(k):
	n = int(input())
	if n % 2 == 1:
		print('0')
		continue
	z = math.factorial(int(n / 2)) ** 2 % 998244353
	print(str(z))


from math import factorial

def solve():
	n = int(input())
	if n % 2 == 0:
		print(factorial(n // 2) ** 2 % 998244353)
	else:
		print(0)
t = int(input())
for i in range(1, t + 1):
	solve()


import math
for i in range(int(input())):
	ab = int(input())
	if ab % 2 != 0:
		print(0)
	else:
		print(math.factorial(ab // 2) ** 2 % 998244353)


from math import factorial
from sys import stdin
input = stdin.readline

def get_string():
	return stdin.readline().strip()

def main():
	for _ in range(int(input())):
		n = int(input())
		if n % 2 != 0:
			print(0)
		else:
			print(factorial(n // 2) ** 2 % 998244353)
main()


from math import factorial
cas = int(input())
lf = []
for i in range(cas):
	n = int(input())
	if n % 2 == 0:
		lf.append(pow(factorial(n // 2), 2) % 998244353)
	else:
		lf.append(0)
for k in range(len(lf)):
	print(lf[k])


import sys
import math
data = sys.stdin.readlines()
numCases = int(data[0])
cases = []
for each in range(1, numCases + 1):
	input_ = data[each].replace('\n', '')
	cases.append(int(input_))
for n in cases:
	if n % 2 == 1:
		print('0')
	else:
		temp = math.factorial(n / 2)
		res = temp * temp % 998244353
		print(res)


from math import factorial
t = int(input())
for x in range(t):
	n = int(input())
	if n % 2 == 1:
		print(0)
		continue
	print(factorial(n // 2) ** 2 % 998244353)


import math as m

def ab(n):
	if n % 2 == 1:
		return 0
	x = n // 2
	xx = m.factorial(x)
	return xx * xx % 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	print(ab(n))


mod = 998244353

def find(n):
	ans = 1
	for i in range(1, n + 1):
		ans = ans * i % mod
	return ans
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		f = find(n // 2)
		ans = f * f % mod
		print(ans)


mod = 998244353
from sys import stdin, stdout

def fact(n):
	f = 1
	for i in range(1, n + 1):
		f = f * i % mod
	return f
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	if n & 1:
		print(0)
		continue
	f = fact(n // 2)
	print(f * f % mod)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	if n % 2 == 1:
		print(0)
	else:
		MOD = 998244353
		r = 1
		for i in range(2, n // 2 + 1):
			r = r * i % MOD
		print(r * r % MOD)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()