B. Random Nim Game

Problem Description

Nim is a two-player mathematic game of strategy in which players take turns removing stones from distinct heaps. On each turn, a player must remove at least one stone, and may remove any number of stones provided they all come from the same heap. The person who makes the last move (i.e., who takes the last stone) wins. Alice and Bob is tired of playing Nim under the standard rule, so they want to play Nim randomly. On each turn, a player must select any one of the heaps. Assuming the heap he selects contains $x$ stones, he will randomly choose a integer number $y$ from $[1, x]$, and remove $y$ stone(s) from the heap. Note that the selected heap can be arbitrary. Alice will play first. Calculate the probability of Alice winning, modulo $998244353$.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 500$) - the number of test cases. Description of the test cases follows. The first line of each test case contains one integer $n$ ($1 \le n \le 10 ^ 5$) - the number of heap(s). The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10 ^ 9$) - the number of stone(s) of each heap. It's guaranteed that $\sum n \le 10 ^ 6$.

Output

For each test case, print a single integer - the probability of Alice winning, modulo $998244353$.

Sample Input

2
2
1 1
1
2

Sample Output

0
499122177

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）