题目大意：给一个序列，支持区间求 phi、区间赋值、区间求和。

\(n,m\leq 3* 10^5,A_i\leq10^7\)

线段树直接暴力。

一个数在不断变成它的欧拉函数若干次之后恒为一，且许多数的欧拉函数值都是相同的。这样的话，如果我们将修改操作进行改进，只有在当前区间在询问区间以内且当前区间中的数都相同时，我们才对这个区间进行修改，否则我们继续对其的左右儿子进行修改。

#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#define LL long long
const int inf = 1e9 + 9;
const int N = 3e5 + 5;
const int M = 10000000 + 5;
using namespace std;
inline int read() {
    int s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')
            w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
using namespace std;
LL phi[M],pn[M];
bool vis[M];
int n,m,a[N],tot;
void init(){
    phi[1] = 1;
    for(int i = 2;i <= M - 5;i++){
        if(!vis[i]) pn[++tot] = i,phi[i] = i - 1;
        for(int j = 1;j <= tot;++j){
            if(i * pn[j] > M - 5)break;
            vis[i * pn[j]] = 1;
            if(i % pn[j] == 0){
                phi[i * pn[j]] = phi[i] * pn[j];
                break;
            }
            phi[i * pn[j]] = phi[i] * (pn[j] - 1);
        }
    }
}
namespace Segment{
    struct node{
        int l,r;
        LL sum,num;
    }t[N<<2];
    #define ls (k<<1)
    #define rs (k<<1|1)
    #define mid (t[k].l + t[k].r>>1)
    void pushup(int k){
        t[k].sum = t[ls].sum + t[rs].sum;
        t[k].num = t[ls].num == t[rs].num ? t[ls].num : 0;
    }
    void pushnow(int k,LL v){
        t[k].num = v;
        t[k].sum = v * (t[k].r - t[k].l + 1);
    }
    void pushdown(int k){
        if(!t[k].num) return;
        pushnow(ls,t[k].num),pushnow(rs,t[k].num);
    }
    void build(int k,int l,int r){
        t[k].l = l,t[k].r = r;
        if(l == r){
            t[k].num = t[k].sum = a[l];
            return;
        }
        build(ls,l,mid);
        build(rs,mid + 1,r);
        pushup(k);
    }
    void modify(int k,int l,int r){
        if(r < t[k].l || t[k].r < l) return;
        if(l <= t[k].l && t[k].r <= r && t[k].num){
            pushnow(k,phi[t[k].num]);
            return;
        }
        pushdown(k);
        if(r <= mid) modify(ls,l,r);
        else if(l > mid) modify(rs,l,r);
        else modify(ls,l,mid),modify(rs,mid + 1,r);
        pushup(k);
    }
    void update(int k,int l,int r,LL v){
        if(r < t[k].l || t[k].r < l) return;
        if(l <= t[k].l && t[k].r <= r){
            pushnow(k,v);
            return;
        }
        pushdown(k);
        if(r <= mid) update(ls,l,r,v);
        else if(l > mid) update(rs,l,r,v);
        else update(ls,l,mid,v),update(rs,mid+1,r,v);
        pushup(k);
    }
    inline LL query(int k,int l,int r){
        if(r < t[k].l || t[k].r < l) return 0;
        if(l <= t[k].l && t[k].r <= r) return t[k].sum;
        pushdown(k);
        if(r <= mid) return query(ls,l,r);
        if(l > mid) return query(rs,l,r);
        return query(ls,l,mid) + query(rs,mid+1,r);
    }
}
using namespace Segment;
void pre(){
    memset(t,0,sizeof(t));
    n = read(),m = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    build(1,1,n);
    return ;
}
void solve(){
    int op = read(),l = read(),r = read();
    if(op == 1) modify(1,l,r);
    if(op == 2){
        LL v = read();
        update(1,l,r,v);
    }
    if(op == 3) printf("%lld\n",query(1,l,r));
    return ;
}
int main(){
    init();
    int T = read();
    while(T--){
        pre();
        while(m--) solve();
    }
    return 0;
}