#include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 3e5 + ;

 const int MAXM = 1e7 + ;

 const ll mod = 1e9 + ;

 bool check[MAXM];

 int phi[MAXM], prime[MAXM / ], tot;

 void init(int N) {

     tot = ;

     phi[] = ;

     for(int i = ; i <= N; i++) {

         if(!check[i]) {

             prime[tot++] = i;

             phi[i] = i - ;

         }

         for(int j = ; j < tot; j++) {

             if(i * prime[j] > N) break;

             check[i * prime[j]] = true;

             if(i % prime[j] == ) {

                 phi[i * prime[j]] = phi[i] * prime[j];

                 break;

             } else phi[i * prime[j]] = phi[i] * (prime[j] - );

         }

     }

 }

 int a[MAXN],num[MAXN<<];

 ll sum[MAXN<<];

 void pushup(int rt) {

     sum[rt] = sum[rt<<] + sum[rt<<|];

     if(num[rt<<] == num[rt<<|]) num[rt] = num[rt<<];

     else num[rt] = ;

 //    num[rt] = (num[rt<<1] == num[rt<<1|1]) ? num[rt] : 0;

 }

 void build(int rt,int l,int r) {

     if(l == r) {

         sum[rt] = num[rt] = a[l];

         return ;

     }

     int mid = (l + r) >> ;

     build(rt<<,l,mid);

     build(rt<<|,mid + ,r);

     pushup(rt);

 }

 void pushdown(int rt,int l,int r) {

     if(num[rt]) {

         int mid = (l + r) >> ;

         num[rt<<] = num[rt<<|] = num[rt];

         sum[rt<<] = 1ll * num[rt<<] * (mid - l + );

         sum[rt<<|] = 1ll * num[rt<<|] * (r - mid);

         num[rt] = ;

     }

 }

 void update1(int rt,int l,int r,int ql,int qr) {

     if(ql > qr) return ;

     if(num[rt] && l == ql && r == qr) {

         num[rt] = phi[num[rt]];

         sum[rt] = 1ll * num[rt] * (r - l + );

         return ;

     }

     pushdown(rt,l,r);

     int mid = (l + r) >> ;

     if(qr <= mid) update1(rt<<,l,mid,ql,qr);

     else if(ql > mid) update1(rt<<|,mid + ,r,ql,qr);

     else {

         update1(rt<<,l,mid,ql,mid);

         update1(rt<<|,mid + ,r,mid + ,qr);

     }

     pushup(rt);

 }

 void update2(int rt,int l,int r,int ql,int qr,int val) {

     if(ql > qr) return ;

     if(l == ql && r == qr) {

         num[rt] = val;

         sum[rt] = 1ll * num[rt] * (r - l + );

         return ;

     }

     pushdown(rt,l,r);

     int mid = (l + r) >> ;

     if(qr <= mid) update2(rt<<,l,mid,ql,qr,val);

     else if(ql > mid) update2(rt<<|,mid + ,r,ql,qr,val);

     else {

         update2(rt<<,l,mid,ql,mid,val);

         update2(rt<<|,mid + ,r,mid + ,qr,val);

     }

     pushup(rt);

 }

 ll query(int rt,int l,int r,int ql,int qr) {

     if(ql == l && qr == r) return sum[rt];

     pushdown(rt,l,r);

     int mid = (l + r) >> ;

     if(qr <= mid) return query(rt<<,l,mid,ql,qr);

     else if(ql > mid) return query(rt<<|,mid + ,r,ql,qr);

     else return query(rt<<,l,mid,ql,mid) + query(rt<<|,mid + ,r,mid + ,qr);

 }

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     init(1e7);

     int t;

     scanf("%d",&t);

     while(t--) {

         int n,m;

         scanf("%d%d",&n,&m);

         for(int i = ; i <= n; i++) scanf("%d",&a[i]);

         build(,,n);

         while(m--) {

             int op,l,r,x;

             scanf("%d",&op);

             if(op == ) {

                 scanf("%d%d",&l,&r);

                 update1(,,n,l,r);

             } else if(op == ) {

                 scanf("%d%d%d",&l,&r,&x);

                 update2(,,n,l,r,x);

             } else if(op == ) {

                 scanf("%d%d",&l,&r);

                 printf("%lld\n",query(,,n,l,r));

             }

         }

     }

     return ;

 }