题目描述

在一个神秘的魔法大陆上，存在着n座闪耀的城市，它们如同星辰般点缀在大地之上，分别以1,2,3……n 作为其独特的标识。

大陆的魔法师们怀着对二进制魔法的钟爱，赋予每座城市一个独特的魔法数字。第i座城市的魔法数字由 神秘的数字ai决定。根据一种古老的魔法规则，对于任意两座城市i,j(i<j)，从城市i通往城市j 的传 送门数量由F(ai&aj)决定。 现在，魔法师们希望探寻从城市1 出发前往城市n的所有可能路径的数量。然而，这个数字可能会因为 路径的复杂度而变得庞大。为了简化问题，你需要计算答案对998244353取模后的结果。 这个神秘的函数F(x)表示x的二进制表示中1的个数

输入格式

第一行输入一个正整数T，表示数据组数。 对于每一组数据，第一行输入一个正整数n，表示城市数。 第二行输入n个正整数a1,a2……an。

输出格式

对于每一组数据，输出一行一个整数，表示从城市1到城市n的路径数，对998244353取余数之后 的结果。

样例输入 1

3
4
2 3 3 1
5
1 1 1 1 2
10
213672 382909 212809 216719 213980 121009 213899 220021 289002 120390

输出样例

4
0
12433985