I. Random Remainders
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ random positive integers: $$$a_1, a_2, \ldots, a_n$$$. Your task is to compute the following sum: $$$$$$ \sum_{i=1}^n \sum_{j=1}^n (a_i \bmod a_j)^2 $$$$$$

Input

The first line of input contains the number of test cases: $$$Z$$$ ($$$1 \leq Z \leq 1000$$$). The descriptions of the test cases follow.

The first line of a test case contains the length of the sequence $$$n$$$ ($$$1 \leq n \leq 200\,000$$$). The second line contains the sequence – $$$n$$$ positive integers separated by spaces. Each of them was pseudo-randomly generated, uniformly from range $$$[1,10^{12}]$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$400\,000$$$.

Output

For each test case print the required sum modulo $$$998244353$$$.

Example
Input
1
2
3 5
Output
13
Note

$$$(3\bmod 3)^2+(5\bmod 3)^2+(3\bmod 5)^2+(5\bmod 5)^2=0+4+9+0=13$$$.