CF2226F.Inversion Invasion

There is an array $a$ of length $n$. Initially, $a_i = 0$ for all $1 \le i \le n$.

A permutation$^{\text{∗}}$ $p$ is said to be valid if at least one of the following conditions is satisfied for every $1 \le i \le n$:

• $a_i = 0$.
• $\gcd(p_i, n) = a_i$.

You have to process $q$ queries. In each query, you are given two integers $i$ and $x$, and you must update the array by setting $a_i:= x$ persistently.

It is guaranteed that $a_i = 0$ at the time of each query, and it is guaranteed that $x$ divides $n$.

After performing each query, output the sum of the number of inversions$^{\text{†}}$ across all valid permutations. As the answers can be very large, report them modulo $998\,244\,353$.

$^{\text{∗}}$A permutation of length $m$ is an array consisting of $m$ distinct integers from $1$ to $m$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($m=3$ but there is a $4$ in the array).

$^{\text{†}}$An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i \lt j$ and $p_i \gt p_j$. For example, the permutation $[4, 1, 3, 2]$ has $4$ inversions: $(1, 2)$, $(1, 3)$, $(1, 4)$, and $(3, 4)$.

有一个长度为 $n$ 的数组 $a$。初始时，对所有 $1 \le i \le n$，均有 $a_i = 0$。

一个排列$^{\text{∗}}$ $p$ 被称为合法的，当且仅当对每个 $1 \le i \le n$，以下两个条件中至少有一个成立：

• $a_i = 0$；
• $\gcd(p_i, n) = a_i$。

你需要处理 $q$ 个查询。在每个查询中，你将收到两个整数 $i$ 和 $x$，并需持久化地更新数组：令 $a_i := x$。

保证每次查询时均有 $a_i = 0$，且保证 $x$ 是 $n$ 的约数。

每次执行查询后，请输出所有合法排列的逆序对总数（即：对每个合法排列 $p$，计算其逆序对数量，再将所有这些数量求和）。由于答案可能非常大，请对 $998\,244\,353$ 取模后输出。

$^{\text{∗}}$ 长度为 $m$ 的排列是指由 $1$ 到 $m$ 中互不相同的 $m$ 个整数组成的任意顺序的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $m=3$，但数组中出现了 $4$）。

$^{\text{†}}$ 排列 $p$ 中的一个逆序对是指一对下标 $(i, j)$，满足 $i \lt j$ 且 $p_i \gt p_j$。例如，排列 $[4, 1, 3, 2]$ 包含 $4$ 个逆序对：$(1, 2)$、$(1, 3)$、$(1, 4)$ 和 $(3, 4)$。

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 testcase contains two integers $n$ and $q$ ($1 \le n \le 2 \cdot 10^6$; $1 \le q \le \min(n, 10^6)$) — the length of the array $a$ and the number of queries.

Each of the next $q$ lines contains two integers $i$ and $x$ ($1 \le i \le n$; $1 \le x \le n$).

It is guaranteed that $a_i = 0$ at the time of each query, and it is guaranteed that $x$ divides $n$.

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2 \cdot 10^6$, and the sum of $q$ over all the test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 2 \cdot 10^6$；$1 \le q \le \min(n, 10^6)$）—— 分别表示数组 $a$ 的长度和查询次数。

接下来的 $q$ 行中，每行包含两个整数 $i$ 和 $x$（$1 \le i \le n$；$1 \le x \le n$）。

保证在每次查询时均有 $a_i = 0$，且保证 $x$ 整除 $n$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^6$，且所有测试用例的 $q$ 之和不超过 $10^6$。

For each testcase, print $q$ integers — the total number of inversions across all valid permutations after processing each query.

As the answers can be large, print them modulo $998\,244\,353$.

对于每个测试用例，输出 $q$ 个整数——即在处理每个查询后，所有有效排列中逆序对的总数。

由于答案可能很大，请对 $998\,244\,353$ 取模后输出。

For the first testcase, initially, $a = [0, 0, 0]$.

After the first query, $a = [0, 3, 0]$. The valid permutations are $[1, 3, 2]$ and $[2, 3, 1]$. The total number of inversions is $1 + 2 = 3$.

After the second query, $a = [0, 3, 3]$. There are no valid permutations.

对于第一个测试用例，初始时 $a = [0, 0, 0]$。

第一次查询后，$a = [0, 3, 0]$。有效的排列为 $[1, 3, 2]$ 和 $[2, 3, 1]$。逆序对总数为 $1 + 2 = 3$。

第二次查询后，$a = [0, 3, 3]$。不存在有效的排列。