题目描述

Starlight Glimmer 有一个长度为 $n$ 的魔法数列 $v_1,v_2,v_3,\dots,v_n$ ，她可以对这个数列进行以下操作无限次：

• 选择两个下标 $i,j$ ( $1\le i,j\le n$ )，设置 $x\leftarrow \gcd(v_i,v_j)$ 、 $y\leftarrow \textrm{lcm}(v_i,v_j)$ ，然后执行 $v_i\leftarrow x, v_j\leftarrow y$ 。

其中 $\gcd(x,y)$ 表示两个正整数 $x,y$ 的最大公约数， $\textrm{lcm}(x,y)$ 表示两个正整数 $x,y$ 的最小公倍数。

现在她想知道运算后这个数列之和的最大值是多少，即 $\max\sum v_i$ ，为了避免答案过大，需要对 $998244353$ 进行取模。

输入格式

有多个测试用例。第一行包含一个整数 $T$ ( $1\le T\le 10^6$ )，表示每个测试用例的测试用例数：

第一行包含一个整数 $n$ ( $1\le n\le 10^6$ ) 表示魔法序列的长度。

第二行包含 $n$ 个整数 $v_1, v_2, \ldots, v_n$ ( $1\le v_i\le 10^6$ )，表示神奇序列。

保证所有数据中 $n$ 的总和不超过 $10^6$。

输出格式

为每个测试用例打印一个整数，表示最大和取模 $998244353$ 。

3
5
1 4 5 2 10
5
2 4 8 16 32
6
9 6 4 27 10 12

34
62
590