传统题 1000ms 256MiB

集合求和

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为 nn 的序列 aa,对于两个整数集合 A,BA,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\}$。

答案对 998244353998244353 取模。

Format

Input

多组测试数据。

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

接下来 tt 组测试数据,每组测试数据共两行。

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

第二行 nn 个整数表示 ai(109ai109)a_i(-10^9\le a_i\le 10^9)

Output

输出共 tt 行,每行一个整数表示答案。

Samples

123 500
623

Note

牛客小白月赛 F

zstu 2025 校赛 test

未参加
状态
已结束
规则
ACM/ICPC
题目
8
开始于
2025-3-16 22:00
结束于
2025-4-5 22:00
持续时间
480 小时
主持人
参赛人数
1