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

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

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.