Tatooine is a desert planet located at the edge of the Galaxy, and it is not under the jurisdiction of the Galactic Republic. Therefore, there are a few special points in the payment methods there. Merchants not only do not accept the credit methods of the Republic but also do not accept ..... change.

Obi-Wan learned about this the first time he came here, so he prepared ~n~ coins with denominations ~a_1, a_2, \dots, a_n~. He will choose ~l, r~ (~1 \leq l \leq r \leq n~) and bring the coins ~a_l, a_{l + 1}, \dots, a_r~ for his return to Tatooine. Obi-Wan defines ~f(l, r)~ as the smallest amount of money that he cannot pay with the coins ~a_l, a_{l + 1}, \dots, a_r~.

For example, if ~a = [1, 3, 2]~, then ~f(1, 3) = 7~ (because Obi-Wan can pay every amount from ~1~ to ~6~ but does not have enough money to pay ~7~), and ~f(1, 2) = 2~ (although Obi-Wan has enough money to pay the amount ~2~, he still cannot pay because change is not accepted on Tatooine).

Feeling that calculating a single value is too simple, Obi-Wan wants to calculate the sum of ~f~ for all pairs of positive integers ~(l, r)~ such that ~1 \leq l \leq r \leq n~, formally ~\sum_{l=1}^{n}\sum_{r=l}^{n} f(l, r)~.

Can you help him?

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^4~). The description of the test cases is as follows.

The first line of each test case contains an integer ~n~ (~1 \leq n \leq 10^6~), the number of coins that Obi-Wan prepared.

The second line contains ~n~ positive integers ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 10^{12}~), the denominations of Obi-Wan's coins.

The sum of ~n~ over all test cases does not exceed ~10^6~.

Output

For each test case, print a single line with the ~\sum_{l=1}^{n}\sum_{r=l}^{n}f(l, r)~. Since the answer can be very large, you only need to output it in modulo ~998244353~.

Sample Input 1

3
6
1 3 5 7 9 1
6
1 2 4 8 16 32
10
9 7 5 3 1 1 3 5 7 9

Sample Output 1

57
141
615