CF2264E2 A Prime Flood (Hard Version)

这是该问题的困难版本。两个版本的区别在于，本版本中 $n \le 3\cdot 10^5$。只有解决了该问题的所有版本，你才能进行 hack。 Antigun 和 Lamus 淹没了 Madamant 的房子。她希望他们在尽可能少排水的情况下使水位相等。 形式化地，初始水位由一个数组 $a = [a_1, a_2, \ldots, a_n]$ 给出。对于每次假设的清理，Antigun 和 Lamus 选择 $a$ 的一个非空子序列 $^{\text{∗}}$ $b$。他们可以对 $b$ 执行以下操作任意次，包括零次： - 选择一个质数 $p$； - 将所有当前值能被 $p$ 整除的元素 $b_i$ 同时减 $1$。其他元素保持不变。 令 $f(b)$ 为最大的整数 $x$，使得经过若干次操作后，$b$ 中的每个元素都等于 $x$。 求 $a$ 的所有非空子序列 $b$ 的 $f(b)$ 之和，对 $998\,244\,353$ 取模。即使值相同，由不同下标选择形成的子序列也分别计数。 每个子序列独立考虑，从其原始值开始。 $^{\text{∗}}$ 如果序列 $a$ 可以通过从任意位置删除若干（可能为零或全部）元素从序列 $b$ 得到，则称 $a$ 是 $b$ 的子序列。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。测试用例描述如下。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 300\,000$）——数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $300\,000$。

对于每个测试用例，输出一个整数——$a$ 的所有非空子序列 $b$ 的 $f(b)$ 之和，对 $998\,244\,353$ 取模。

在第一个测试用例中，唯一的非空子序列是 $[1]$，不需要任何操作。因此，它的贡献为 $f([1]) = 1$。 在第二个测试用例中，仅包含 $4$ 的出现位置的 $2^3 - 1 = 7$ 个非空子序列贡献为 $4 \cdot 7 = 28$。子序列 $[2]$ 贡献为 $2$。包含值 $2$ 和至少一个 $4$ 的出现位置的 $7$ 个子序列中，每个都有 $f(b) = 1$。因此，答案为 $28 + 2 + 7 = 37$。