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)$.

Input

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$.

Output

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$.

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.