#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N = 300500;
const int M = 1050000;
const int MN = 10000001;
struct Node
{
    Node *lson,*rson;
    int l,r,mid,tot;
    long long val;
    int lan;
    bool same;
}tree[M];
int dr[N];
int n,m;
int phi[MN];
bool notprime[MN];
int prime[MN];
int getint()
{
    int res=0;
    char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-')
        ch=getchar();
    bool fan=0;
    if(ch=='-')
    {
        fan=1;
        ch=getchar();
    }
    while('0'<=ch && ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    if(fan)
        res=-res;
    return res;
}
void Init()
{
    int i,j;
    phi[1]=1;
    for(i=2;i<MN;i++)
    {
        if(!notprime[i])
        {
            prime[++prime[0]]=i;
            phi[i]=i-1;
        }
        for(j=1;j<=prime[0];j++)
        {
            int now=prime[j];
            int mul=now*i;
            if(mul>=MN)
                break;
            notprime[mul]=1;
            if(i%now==0)
            {
                phi[mul]=phi[i]*now;
                break;
            }
            phi[mul]=phi[i]*(now-1);
        }
    }
}
void Replace(Node *x)
{
    x->val=x->lson->val+x->rson->val;
    x->same=0;
    if(x->lson->same && x->rson->same)
    {
        if(x->lson->val/x->lson->tot==x->rson->val/x->rson->tot)
            x->same=1;
    }
}
void MakeTree(int x,int l,int r)
{
    tree[x].l=l;
    tree[x].r=r;
    tree[x].lan=0;
    tree[x].tot=r-l+1;
    if(l<r)
    {
        int mid=(l+r)/2;
        tree[x].mid=mid;
        tree[x].lson=tree+(x*2);
        tree[x].rson=tree+(x*2+1);
        MakeTree(x*2,l,mid);
        MakeTree(x*2+1,mid+1,r);
        Replace(tree+x);
    }
    else
    {
        tree[x].same=1;
        tree[x].val=dr[l];
    }
}
void GetData()
{
    int i;
    n=getint();
    m=getint();
    for(i=1;i<=n;i++)
        dr[i]=getint();
    MakeTree(1,1,n);
}
void ChangeX(Node *x,int y)
{
    x->lan=y;
    x->same=1;
    x->val=x->tot;
    x->val*=y;
}
void Clear(Node *x)
{
    if(x->lan)
    {
        ChangeX(x->lson,x->lan);
        ChangeX(x->rson,x->lan);
        x->lan=0;
    }
}
void PhiX(Node *x)
{
    if(x->same)
    {
        ChangeX(x,phi[x->val/x->tot]);
    }
    else
    {
        PhiX(x->lson);
        PhiX(x->rson);
        Replace(x);
    }
}
void Phi(Node *x,int l,int r)
{
    if(x->l==l && x->r==r)
    {
        PhiX(x);
    }
    else
    {
        Clear(x);
        if(r<=x->mid)
        {
            Phi(x->lson,l,r);
        }
        else if(l>x->mid)
        {
            Phi(x->rson,l,r);
        }
        else
        {
            Phi(x->lson,l,x->mid);
            Phi(x->rson,x->mid+1,r);
        }
        Replace(x);
    }
}
void Change(Node *x,int l,int r,int t)
{
    if(x->l==l && x->r==r)
    {
        ChangeX(x,t);
    }
    else
    {
        Clear(x);
        if(r<=x->mid)
        {
            Change(x->lson,l,r,t);
        }
        else if(l>x->mid)
        {
            Change(x->rson,l,r,t);
        }
        else
        {
            Change(x->lson,l,x->mid,t);
            Change(x->rson,x->mid+1,r,t);
        }
        Replace(x);
    }
}
long long Find(Node *x,int l,int r)
{
    if(x->l==l && x->r==r)
    {
        return x->val;
    }
    else
    {
        Clear(x);
        if(r<=x->mid)
        {
            return Find(x->lson,l,r);
        }
        else if(l>x->mid)
        {
            return Find(x->rson,l,r);
        }
        else
        {
            return Find(x->lson,l,x->mid)+Find(x->rson,x->mid+1,r);
        }
    }
}
void DoIt()
{
    while(m--)
    {
        int opt=getint();
        if(opt==1)
        {
            int l=getint();
            int r=getint();
            Phi(tree+1,l,r);
        }
        else if(opt==2)
        {
            int l=getint();
            int r=getint();
            int t=getint();
            Change(tree+1,l,r,t);
        }
        else
        {
            int l=getint();
            int r=getint();
            long long res=Find(tree+1,l,r);
            printf("%I64d\n",res);
        }
    }
}
void f()
{
    GetData();
    DoIt();
}
int main()
{
    Init();
    int T=getint();
    while(T--)
        f();
    return 0;
}