Prime Reduction#13085
Fady loves playing with arrays. He is given an array consisting of positive integers. His ultimate goal is to reduce every element in the array to exactly using the minimum number of operations.
In a single operation, Fady can:
Choose a prime number .
Choose a contiguous subsegment [l, r] (1 \le l \le r \le n) such that every element a_i in the subsegment (l \le i \le r) is a multiple of .
Divide each element a_i in the chosen subsegment by .
Fady's friend challenges him by repeatedly modifying the array. There are updates. In each update, Fady is given two integers and , meaning he must update the element at index to (a_{idx} = x).
After each update, find the minimum number of operations needed to make all elements of the array equal to .
The updates are cumulative. The operations are not actually performed and do not affect subsequent updates.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
The first line of each test case contains two integers and (1 \le n, q \le 5 \cdot 10^5) — the size of the array and the number of updates.
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^7) — the initial elements of the array.
Then lines follow. Each line contains two integers and (1 \le idx \le n, 1 \le x \le 10^7), describing an update.
It is guaranteed that the sum of over all test cases does not exceed 5 \cdot 10^5, and the sum of over all test cases does not exceed 5 \cdot 10^5.
For each test case, output lines. The -th line should contain a single integer — the minimum number of operations Fady requires to make all elements in the array equal to after the -th update.
Example 1
In the first test case, the initial array is a = [12, 6, 12, 2].
After the first update, the array becomes a = [12, 1, 12, 2]. The minimum number of operations is :
Apply operations to a_1 (p \in \{2, 2, 3\}).
Apply operations to the subsegment . The operation p=2 is applied to both a_3 and a_4 simultaneously, while p \in \{2, 3\} are applied only to a_3.
After the second update, the array becomes a = [12, 1, 2, 2]. The minimum number of operations is :
Apply operations to a_1 (p \in \{2, 2, 3\}).
Apply operation to the subsegment (p=2).
In the second test case, the array is initially a = [30, 30, 30]. After the first update, it becomes a = [30, 1, 30]. Since a_2 = 1, the remaining elements cannot share operations. We apply operations (p \in \{2, 3, 5\}) to a_1 and operations to a_3, totaling operations.
Subtask ( points): \sum n \le 2000 and \sum q \le 2000.
Subtask ( points): 1 \le a_i, x \le 1000.
Subtask ( points): No additional constraints.