说明

你正在玩 最大公约数牌组构建游戏（GCDDCG）。游戏中有 $N$ 张卡牌（编号从 $1$ 到 $N$）。第 $i$ 张卡牌有一个值 $A_i$，它是一个介于 $1$ 到 $N$（含）之间的整数。

游戏包含 $N$ 轮（编号从 $1$ 到 $N$）。在每一轮中，你需要构建两个非空的牌堆：牌堆 $1$ 和牌堆 $2$。一张卡牌不能同时属于两个牌堆，并且允许不使用所有 $N$ 张卡牌。在第 $i$ 轮中，每个牌堆中卡牌值的最大公约数 (GCD) 必须等于 $i$。

你在第 $i$ 轮的创造力点数是 $i$ 与构建两个有效牌堆的方案数的乘积。如果两个方案中有一个牌堆包含的卡牌不同，则认为它们是不同的方案。

请计算所有 $N$ 轮的创造力点数之和。由于总和可能非常大，请将结果对 $998\,244\,353$ 取模后输出。

输入格式

第一行包含一个整数 $N$（$2 \leq N \leq 200\,000$）。

第二行包含 $N$ 个整数 $A_i$（$1 \leq A_i \leq N$）。

输出格式

输出一个整数，表示所有 $N$ 轮的创造力点数之和模 $998\,244\,353$ 的结果。

3
3 3 3

36

4
2 2 4 4

44

9
4 2 6 9 7 7 7 3 3

10858

提示

样例输入/输出 #1 的解释

第 $1$ 轮和第 $2$ 轮的创造力点数均为 $0$。

在第 $3$ 轮中，构建两个牌堆共有 $12$ 种方案。记 $B$ 和 $C$ 分别为牌堆 $1$ 和牌堆 $2$ 中的卡牌编号集合。构建两个牌堆的 $12$ 种方案如下：

• $B = \{ 1 \}, C = \{ 2 \}$；
• $B = \{ 1 \}, C = \{ 3 \}$；
• $B = \{ 1 \}, C = \{ 2, 3 \}$；
• $B = \{ 2 \}, C = \{ 1 \}$；
• $B = \{ 2 \}, C = \{ 3 \}$；
• $B = \{ 2 \}, C = \{ 1, 3 \}$；
• $B = \{ 3 \}, C = \{ 1 \}$；
• $B = \{ 3 \}, C = \{ 2 \}$；
• $B = \{ 3 \}, C = \{ 1, 2 \}$；
• $B = \{ 1, 2 \}, C = \{ 3 \}$；
• $B = \{ 2, 3 \}, C = \{ 1 \}$；
• $B = \{ 1, 3 \}, C = \{ 2 \}$。

样例输入/输出 #2 的解释

对于第 $1$、$2$、$3$ 和 $4$ 轮，构建两个牌堆的方案数分别为 $0$、$18$、$0$ 和 $2$。

翻译由 DeepSeek V3.2 完成