#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#define Np 700     #define LL __int64using namespace std;bool isprime[Np];LL prime[Np],np;LL dsorp[Np],dp;struct Update{	LL pos,val;};Update up[1500];LL upp;void initial(){	memset(isprime,true,sizeof(isprime));	np=0;	isprime[1]=false;	for(LL i=2;i<Np;i++){		if(isprime[i]){			prime[np++]=i;			for(LL j=i*i;j<Np;j+=i){				isprime[j]=false;			}		}	}}void dfs(LL i,LL num,LL tmp,LL &s,LL n){	if(i>=dp){		if(num==0){			s=(1+n)*n/2;		}		else{			LL sc=n/tmp;			if(num&1){				s=s-((sc+1)*sc/2*tmp);			}			else{				s=s+((sc+1)*sc/2*tmp);			}		}		return;	}	dfs(i+1,num,tmp,s,n);	dfs(i+1,num+1,tmp*dsorp[i],s,n);}LL work(LL x,LL y,LL p){	dp=0; 	for(LL i=0;i<np&&prime[i]*prime[i]<=p;i++){		if(p%prime[i]==0){			dsorp[dp++]=prime[i];			while(p%prime[i]==0)			p=p/prime[i];		}	}	if(p>1)	dsorp[dp++]=p;	LL ansy,ansx;	ansy=ansx=0;	dfs(0,0,1,ansy,y);	dfs(0,0,1,ansx,x-1);	return ansy-ansx;}LL gcd(LL a,LL b){	if(b==0) return a;	return gcd(b,a%b);}bool coprime(LL a,LL p){	if(gcd(a,p)==1LL)	return true;	else return false;}int main(){	LL T,n,m,op,x,y,p,c;	initial();	scanf("%I64d",&T);	while(T--){		scanf("%I64d%I64d",&n,&m);		upp=0;		for(LL i=1;i<=m;i++){			scanf("%I64d",&op);			if(op==1LL){				scanf("%I64d%I64d%I64d",&x,&y,&p);				LL ans=work(x,y,p);				for(LL k=0;k<upp;k++){					if(up[k].pos>=x&&up[k].pos<=y){						bool flag1=coprime(up[k].pos,p);						bool flag2=coprime(up[k].val,p);						if(flag1){							if(flag2){								ans=ans-up[k].pos+up[k].val;							}							else							ans=ans-up[k].pos;						}						else{							if(flag2)							ans=ans+up[k].val;						}					}				}				printf("%I64d\n",ans);			}			else{				scanf("%I64d%I64d",&x,&c);				LL i;				for(i=0;i<upp;i++){					if(up[i].pos==x){						up[i].val=c;					}				}				if(i==upp){					up[upp].pos=x;					up[upp].val=c;					upp++;				}			}		}	}	return 0;}

#include <map>#include <stdio.h>typedef __int64 LL;using namespace std;#define N 650bool np[N];int prime[120],fac[9],F_top,p;LL ans;void get_prime(){    int top = -1;    for(int i=2;i<N;i++)        if(!np[i])        {            prime[++top] = i;            for(int j=i+i;j<N;j+=i)                np[j] = true;        }}void Div(int n){    F_top = 0;    for(int i=0;prime[i]*prime[i]<=n;i++)    {        if(n % prime[i])            continue;        while(n % prime[i] == 0)            n /= prime[i];        fac[F_top++] = prime[i];    }    if(n != 1)        fac[F_top++] = n;}LL PreSum(int n){    return (LL)n*(n+1)/2;}void dfs(int i,int cnt,int m,int n,int num,int x)       // C(n,m).{    if(cnt == m)    {        LL sum = num * PreSum(x/num);        m&1 ? ans -= sum : ans += sum;        return ;    }    if(num*fac[i] > x || n-i < m-cnt)        return ;    dfs(i+1,cnt+1,m,n,num*fac[i],x);    dfs(i+1,cnt,m,n,num,x);}LL sovle(int n){    ans = PreSum(n);    for(int m=1;m<=F_top;m++)        dfs(0,0,m,F_top,1,n);    return ans;}int gcd(int a,int b){    return b ? gcd(b,a%b) : a;}int main(){    int z,n,Q,cmd,a,b;    get_prime();    scanf("%d",&z);    map<int,int> M;    while(z--)    {        M.clear();        scanf("%d%d",&n,&Q);        while(Q--)        {            scanf("%d",&cmd);            if(cmd == 1)            {                scanf("%d%d%d",&a,&b,&p);                Div(p);                ans = sovle(b) - sovle(a-1);                for(map<int,int>::iterator it=M.begin();it!=M.end();it++)                    if((*it).first >= a && (*it).first <= b)                    {                        if(gcd((*it).first,p) == 1)                            ans -= (*it).first;                        if(gcd((*it).second,p) == 1)                            ans += (*it).second;                    }                printf("%I64d\n",ans);            }            else            {                scanf("%d%d",&a,&b);                M[a] = b;            }        }    }    return 0;}