Given a non-negative integer array $\{a_i\}$ of length $n$ $(1 \le n \le 2 \times 10^5)$, Little L defines a magical transformation:

$$ f_k = \sum_{i=1}^{n} a_i^k \pmod{998244353} $$

Little L plans to do something interesting with the sequence $f$ generated by this transformation, but he is not good at multiplication, so he has come to you for help. He hopes you can help him calculate $f_1 \sim f_n$ as quickly as possible.

Input

The input contains multiple test cases.

The first line of the input contains an integer $T$ $(1 \le T \le 20)$, representing the number of test cases.

The next $2T$ lines contain the test data, with two lines per test case.

The first line of each test case contains an integer $n$, representing the length of the array $\{a_i\}$. The next line contains $n$ integers describing the array $\{a_i\}$.

It is guaranteed that the input $a_i$ satisfies $0 \le a_i \le 10^9$. In a single test file, it is guaranteed that $\sum n \le 4 \times 10^5$.

Output

We do not want you to output too many numbers. Therefore, let $\text{ans} = f_1 \oplus f_2 \oplus \dots \oplus f_n$, where $\oplus$ denotes the XOR operation, which can be represented as ^ in C++ / Java / Python.

For each test case, you need to output a single integer representing $\text{ans}$.

Examples

Input 1

2
3
2 3 3
5
1 2 3 4 5

Output 1

32
4675