Problem Description

Rikka and Yuta are interested in Phi function (which is known as Euler's totient function).

Yuta gives Rikka an array $A[1..n]$ of positive integers, then Yuta makes $m$ queries.

There are three types of queries:

$ 1 \; l \; r $

Change $A[i]$ into $\varphi(A[i])$, for all $i \in [l, r]$.

$ 2 \; l \; r \; x$

Change $A[i]$ into $x$, for all $i \in [l, r]$.

$ 3 \; l \; r $

Sum up $A[i]$, for all $i \in [l, r]$.

Help Rikka by computing the results of queries of type 3.

Input

The first line contains a number $T(T \leq 100)$ ——The number of the testcases. And there are no more than 2 testcases with $n > 10 ^ 5$

For each testcase, the first line contains two numbers $n,m(n \leq 3 \times 10^5, m \leq 3 \times 10^5)$。

The second line contains $n$ numbers $A[i]$

Each of the next $m$ lines contains the description of the query.

It is guaranteed that $1 \leq A[i] \leq 10^7$ At any moment.

Output

For each query of type 3, print one number which represents the answer.

1
10 10
56 90 33 70 91 69 41 22 77 45
1 3 9
1 1 10
3 3 8
2 5 6 74
1 1 8
3 1 9
1 2 10
1 4 9
2 8 8 69
3 3 9

80
122
86