CF2264E2.A Prime Flood (Hard Version)

This is the Hard version of the problem. The difference between the versions is that in this version, $n \le 3\cdot 10^5$. You can hack only if you solved all versions of this problem.

Antigun and Lamus have flooded Madamant's house. She wants them to make the water levels equal while removing as little water as possible.

Formally, the initial water levels are given by an array $a = [a_1, a_2, \ldots, a_n]$. For each hypothetical cleanup, Antigun and Lamus select a non-empty subsequence$^{\text{∗}}$ $b$ of $a$. They may perform the following operation on $b$ any number of times, possibly zero:

• choose a prime number $p$;
• simultaneously decrease every element $b_i$ whose current value is divisible by $p$ by $1$. All other elements remain unchanged.

Let $f(b)$ be the maximum integer $x$ such that, after some sequence of operations, every element of $b$ is equal to $x$.

Find the sum of $f(b)$ over all non-empty subsequences $b$ of $a$, modulo $998\,244\,353$. Subsequences formed by different choices of indices are counted separately, even if their values are equal.

Each subsequence is considered independently, starting from its original values.

$^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.

这是本题的困难版本。两个版本的区别在于，在本版本中，$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$；
• 同时将 $b$ 中所有当前值能被 $p$ 整除的元素 $b_i$ 减少 $1$；其余元素保持不变。

令 $f(b)$ 表示满足如下条件的最大整数 $x$：经过若干次操作后，$b$ 的每个元素均等于 $x$。

求 $a$ 的所有非空子序列 $b$ 对应的 $f(b)$ 之和，对 $998\,244\,353$ 取模。即使不同下标选取的子序列具有相同元素值，也视为不同的子序列并分别计数。

每个子序列均独立考虑，且均从其原始值开始处理。

$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 的任意位置删除若干个（可能为零个或全部）元素而得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 300\,000$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print one integer — the sum of $f(b)$ over all non-empty subsequences $b$ of $a$, modulo $998\,244\,353$.

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

In the first test case, the only non-empty subsequence is $[1]$, and no operation is needed. Therefore, its contribution is $f([1]) = 1$.

In the second test case, the $2^3 - 1 = 7$ non-empty subsequences containing only occurrences of $4$ contribute $4 \cdot 7 = 28$. The subsequence $[2]$ contributes $2$. Each of the $7$ subsequences containing the value $2$ and at least one occurrence of $4$ has $f(b) = 1$. Hence, the answer is $28 + 2 + 7 = 37$.

在第一个测试用例中，唯一的非空子序列为 $[1]$，且无需进行任何操作。因此，其贡献值为 $f([1]) = 1$。

在第二个测试用例中，所有仅包含数字 $4$ 的出现的 $2^3 - 1 = 7$ 个非空子序列，其贡献值为 $4 \cdot 7 = 28$；子序列 $[2]$ 的贡献值为 $2$；每个包含数字 $2$ 和至少一个 $4$ 的子序列均有 $f(b) = 1$，这样的子序列共 $7$ 个。因此，答案为 $28 + 2 + 7 = 37$。