Marin and Anti-coprime Permutation codeforces solution in c++

 B. Marin and Anti-coprime Permutation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Marin wants you to count number of permutations that are beautiful. A beautiful permutation of length n$n$ is a permutation that has the following property:

gcd(1⋅p1,2⋅p2,…,n⋅pn)>1,$$gcd(1\cdot p_1,2\cdot p_2,\dots ,n\cdot p_n)>1,$$

where gcd$gcd$ is the greatest common divisor.

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

Input

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

Each test case consists of one line containing one integer n$n$ (1≤n≤103$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 998244353$998244353$.

Example

input

Copy

7
1
2
3
4
5
6
1000

output

Copy

0
1
0
4
0
36
665702330

Note

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

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

solution

#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
#define ll long long
using namespace std;
 
void solve()
{
	//B. Marin and Anti-coprime Permutation
 
	ll n;
	cin >> n;
	if (n % 2 ==1)
	{
		cout << 0 << "\n";
	}
	else
	{
		ll sum = 1;
		for (int i = 1; i <= n / 2; i++)
		{
			sum = (i * sum) % 998244353;
			
		}
		
		sum *= sum;
		
		cout << sum % 998244353 << "\n";
	}
}
 
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}