Djangle loves studying array operations!

This time, he has a sequence of $n$ positive integers $a$, and he wants to perform some operations and queries on it. He is very interested in the properties of the gcd (greatest common divisor) and has proposed the following two types of operations, each involving three parameters $l, r, x$:

• Operation 0: Range assignment: Modify all elements in the range $[l, r]$ to a given positive integer $x$, i.e.: $a_i := x, \quad \forall i \in [l, r]$

• Operation 1: GCD query and update:

  • First, calculate the sum of the gcd of all elements in the range $[l, r]$ with a given positive integer $x$, i.e.: $$\sum_{i=l}^{r} \gcd(a_i, x)$$
  • Then, update all elements in the range $[l, r]$ to $\gcd(a_i, x)$, i.e.: $a_i := \gcd(a_i, x), \quad \forall i \in [l, r]$

Djangle is too lazy to calculate the answers himself, so he asks you to help him implement a program.

Input

The first line contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases.

For each test case: The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$, $\sum n, \sum q \le 10^5$), representing the length of the array and the number of operations, respectively. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2^{30}$), representing the initial array. The next $q$ lines each describe an operation: If it is operation 0, the format is 0 l r x, representing changing all elements in the range $[l, r]$ to $x$ ($1 \le x \le 2^{30}$). * If it is operation 1, the format is 1 l r x, representing performing the GCD query and update operation ($1 \le x \le 2^{30}$).

Output

For each operation 1, output the calculated sum of gcds.

Examples

Input 1

2
5 5
32 16 6 34 47
1 3 4 93
0 2 4 46
0 1 2 81
1 3 5 2
1 3 3 69
10 10
974 560 4 870 975 322 233 742 917 611
1 2 6 766
0 2 6 562
1 4 10 920
1 6 10 353
0 7 10 481
0 9 9 207
1 1 3 43
1 1 10 524
1 1 2 710
0 7 10 190

Output 1

4
5
1
9
11
5
3
12
2

Note

For the first test case: