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