问题描述

Gordon 手上有一个长度为 $n$ 的数组 $a$。现在他想知道：

$$\sum_{i=1}^n\sum_{j=1}^n\text{lowbit}(a_i\oplus a_j) $$

其中 $\oplus$ 表示异或运算，$\text{lowbit}$ 函数用于求解某个数在二进制下最低位的 $1$ 所表示的值。

特别的，$0$ 的 $\text{lowbit}$ 值为 $0$。

由于最后的结果可能非常大，所以你需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行为 $T(1\le T\le 10)$，表示数据组数。

对于每组数据，第一行为 $n(1\le n\le 1.5\times 10^4)$。第二行为数组 $a$，数组内元素为不大于 $2^{29}$ 的非负整数。

输出格式

每组数据输出一行，为最后计算出的结果。具体格式参考样例。

2
5
4 0 2 7 0
5
2 6 5 4 0

Case #1: 36
Case #2: 40