Statement : F. 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)$.
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$.
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$.
Input
3
3 2
2 3
3 3
9 3
6 3
7 1
3 3
100 7
67 4
41 25
69 1
99 1
50 100
100 2
9 10
Output
3
0
1461600
1114560
156960
207622048
432575995
443345156
499213668
665624940
770601684
223944735
Note
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.