D. Magic LCM
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Starlight Glimmer has a magic sequence $$$v_1,v_2,v_3,\dots,v_n$$$ of length $$$n$$$, and she can perform the following operations on the sequence an infinite number of times:

  • Select two subscripts $$$i,j$$$ ($$$1\le i,j\le n$$$), set $$$x\leftarrow \gcd(v_i,v_j)$$$, $$$y\leftarrow \textrm{lcm}(v_i,v_j)$$$, then make $$$v_i\leftarrow x, v_j\leftarrow y$$$.

Where $$$\gcd(x,y)$$$ denotes the greatest common divisor of two positive integers $$$x,y$$$ and $$$\textrm{lcm}(x,y)$$$ denotes the least common multiple of two positive integers $$$x,y$$$.

Now she wants to know what the maximum value of the sum of this sequence is after the operation, i.e. $$$\max\sum v_i$$$, and to avoid the answer being too large, you need to modulo $$$998244353$$$ to print it.

Input

There are multiple test cases. The first line contains an integer $$$T$$$ ($$$1\le T\le 10^6$$$) indicating the number of test cases, for each test case:

The first line contains an integer $$$n$$$ ($$$1\le n\le 10^6$$$) indicating the length of magic sequence.

The second line contain $$$n$$$ integers $$$v_1, v_2, \ldots, v_n$$$ ($$$1\le v_i\le 10^6$$$), represents the magic sequence.

It is guaranteed that the sum of $$$n$$$ in all data does not exceed $$$10^6$$$.

Output

For each test case, print a single integer, represents the maximum sum modulo $$$998244353$$$.

Example
Input
3
5
1 4 5 2 10
5
2 4 8 16 32
6
9 6 4 27 10 12
Output
34
62
590