ZYB loves Xor I

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Memphis loves xor very musch.Now he gets an array A.The length of A is n.Now he wants to know the sum of all (lowbit($A_i$ xor $A_j$)) $(i,j \in [1,n])$
We define that lowbit(x)=$2^{k}$,k is the smallest integer satisfied (($x$ and $2^k$)>0)
Specially,lowbit(0)=0
Because the ans may be too big.You just need to output $ans$ mod 998244353

Input

Multiple test cases, the first line contains an integer T(no more than 10), indicating the number of cases. Each test case contains two lines
The first line has an integer $n$
The second line has $n$ integers $A_1$,$A_2$....$A_n$
$n \in [1,5*10^4]$,$A_i \in [0,2^{29}]$

Output

For each case, the output should occupies exactly one line. The output format is Case #x: ans, here x is the data number begins at 1.

Sample Input

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

Sample Output

Case #1: 36 Case #2: 40

Hint

hujie

Source

BestCoder Round #44

提交代码