你正在玩“最大公约数套牌构建卡牌游戏”（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 \le N \le 200\,000$)。 第二行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le N$)。

输出格式

输出一个整数，表示所有 $N$ 个回合的创造力点数之和对 998 244 353 取模的结果。

样例

样例输入 1

3
3 3 3

样例输出 1

36

说明 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

4
2 2 4 4

样例输出 2

44

说明 2

对于第 1、2、3 和 4 回合，构建两个套牌的方法数分别为 0、18、0 和 2。

样例输入 3

9
4 2 6 9 7 7 7 3 3

样例输出 3

10858