3884: 罗dalao的数列
内存限制：128 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：54
解决：13
题目描述
最近，罗dalao想研究一些特殊的数列，他首先找到了一个长度为n的数列a，在这个数列中，对于所有1<=i<=n，有ai=i，他把这个数列打乱重排，得到数列b，他又用a和b两个数列生成数列c，在c中，对于所有1<=i<=n有ci=ai xor bi，他现在想知道，a的长度为n时，要使c1*c2*c3*...*cn不等于0，有多少种不同的b数列满足要求，由于答案会很大，请你输出答案对 998244353 取模的结果
输入
第一行一个整数T代表数据组数(1<=T<=2000000)
对于每组数据，有一行一个整数n表示a数列的长度(1<=n<=1000000)
对于每组数据，有一行一个整数n表示a数列的长度(1<=n<=1000000)
输出
对于每组数据，输出一行一个整数代表答案
样例输入 复制
2
1
2
样例输出 复制
0
1