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.
