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.

Inversion Invasion

Examples