Description

给定一个长度为 $n$ 的序列 $a$，对于两个整数集合 $A,B$，定义 $S(A,B)=\sum\limits_{i=1}^{|A|}a_{A_i},\exist B_j,\gcd(A_i,B_j)\ne 1$。求 $\sum\limits_{A\sub U,B\sub U} S(A,B),U=\{1,2,...,n\}$。

答案对 $998244353$ 取模。

Format

Input

多组测试数据。

第一行一个正整数 $t(1\le t\le 100)$ 表示数据组数。

接下来 $t$ 组测试数据，每组测试数据共两行。

第一行一个正整数 $n(1\le \sum n\le 2\times 10^5)$ 表示序列 $a$ 的大小。

第二行 $n$ 个整数表示 $a_i(-10^9\le a_i\le 10^9)$。

Output

输出共 $t$ 行，每行一个整数表示答案。

Samples

123 500

623

Note

牛客小白月赛 F