Problem Description

给定一个长度为 $n$ 的序列 $a$，求 $\sum_{l=1}^n\sum_{r=l}^n(a_l\bigoplus a_{l+1}\bigoplus \dots\bigoplus a_r)\times\min_{l\leq i\leq r}a_i$ 的值。其中 $\bigoplus$ 表示按位异或。

请输出答案对 $998244353$ 取模后的结果。

Input

测试点包含多组数据。第一行包含一个整数 $T$（$1\leq T\leq 10$），表示数据组数。每组数据的输入格式如下：

第一行包含一个整数 $n$（$1\leq n\leq10^5$），表示序列的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\leq a_i\leq 10^9$）。

Output

每组数据包含一个整数，表示答案对 $998244353$ 取模后的结果。

2
3
2 3 4
5
5 12 18 8 17

62
2219

Hint

样例中的第一组数据，答案为 $2\times2+2\times(2\bigoplus3)+2\times(2\bigoplus3\bigoplus4)+3\times3+3\times(3\bigoplus4)+4\times4=2\times2+2\times1+2\times5+3\times3+3\times7+4\times4=62$