H. GCD Queries with Updates
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$ consisting of positive integers. You have to process $$$q$$$ queries of two types:

  • 1 i g — print the number of indices $$$j$$$ ($$$j \ne i$$$) such that $$$\gcd(a_i,a_j)=g$$$;
  • 2 i x — assign $$$a_i \gets x$$$ (this update affects subsequent queries).

All indices are $$$1$$$-based.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^{3})$$$. The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n \le 10^{5};\ 1 \le q \le 10^{5})$$$. The second line contains $$$n$$$ integers $$$a_1,\dots,a_n$$$ $$$(1 \le a_i \le 10^{6})$$$. Each of the next $$$q$$$ lines is one of:

  • 1 i g $$$(1 \le i \le n;\ 1 \le g \le 10^{6})$$$
  • 2 i x $$$(1 \le i \le n;\ 1 \le x \le 10^{6})$$$
It is guaranteed that $$$\sum n \le 10^{5}$$$ and $$$\sum q \le 10^{5}$$$ over all test cases.
Output

For each query of type 1, print a single integer — the number of indices $$$j$$$ ($$$j \ne i$$$) such that $$$\gcd(a_i,a_j)=g$$$. Print each answer on a separate line.

Example
Input
2
4 2
12 8 9 18
1 1 12
1 4 2
5 10
1 1 2 3 6
1 1 1
1 5 2
2 2 1
2 3 1
1 5 3
1 4 6
2 1 6
1 1 6
2 1 6
1 2 1
Output
0
1
4
1
1
0
1
4
Note

In the first test case, for the first query we need to find elements in the array that satisfy $$$ \gcd(a_i, 12) = 12 \, \forall \, i \neq 1$$$. No such numbers exist in the array so the answer is 0. For the second query we need to find elements such that $$$ \gcd(a_i, 18) = 2 \, \forall \, i \neq 4$$$

In the second test case, for the first query all the numbers in the given array satisfy $$$ \gcd(a_i, 1) = 1$$$, so the answer is 4. For the second query, only $$$a_3 = 2$$$ satisfies $$$ \gcd (6, a_i) = 2$$$. After the third query, the array remains unchanged and after the fourth query it becomes $$$ [1,1,1,3,6] $$$. For the fifth query, only one element $$$ a_4 = 3 $$$ satisfies $$$ \gcd(6, a_j)=3 $$$