G. Max-Min Madness
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. You can perform the following two operations any number of times, in any order:

  1. Choose an index $$$i$$$ such that $$$a_i \gt 0$$$, and decrement $$$a_i$$$ by $$$1$$$. In other words, assign $$$a_i := a_i - 1$$$.
  2. Select $$$k \geq 2$$$ distinct indices $$$i_1, i_2, \dots, i_k$$$ such that there exists at least one pair of indices $$$i_x$$$ and $$$i_y$$$ satisfying $$$a_{i_x} \neq a_{i_y}$$$. In other words, not all the values in the picked indices are the same. Then simultaneously set the values of all of $$$a_{i_1},a_{i_2},\dots,a_{i_k}$$$ to $$$(\max(a_{i_1}, a_{i_2}, \dots, a_{i_k})$$$ $$$- \min(a_{i_1}, a_{i_2}, \dots, a_{i_k}) - 1)$$$.

    For example, given $$$a = [1,0,1,9,1]$$$, choosing $$$a_1, a_3, a_4$$$ for operation $$$2$$$ results in $$$a=[7,0,7,7,1]$$$. However, choosing $$$a_1, a_3, a_5$$$ for operation $$$2$$$ is invalid, as their values are the same.

You want to choose a sequence of operations that maximizes the total number of operations. Find the maximum number of operations possible. Since the answer can be large, output it modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer in a new line — the maximum number of operations possible modulo $$$998\,244\,353$$$.

Example
Input
2
1
5
2
0 2
Output
5
3
Note

In the first test case, you can only choose $$$a_1$$$ for operation $$$1$$$ five times.

In the second test case, the optimal strategy is the following:

  1. Choose $$$a_1$$$ and $$$a_2$$$ for operation $$$2$$$. After that, $$$a=[1,1]$$$.
  2. Choose $$$a_1$$$ for operation $$$1$$$. After that, $$$a=[0,1]$$$.
  3. Choose $$$a_2$$$ for operation $$$1$$$. After that, $$$a=[0,0]$$$.

After this, we can no longer perform any of the two operations on the array.