#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#define N 400010
using namespace std;
typedef long long LL;
map<int , int >mp;
map<int , int>::iterator it;
int p[N][15]={0}; // 二维记录p二维质因子
int num[N]={0};  // 记录P二维质因子的个数
int IsNotPrime[N]={0};
LL ans;

// 筛选得到 质因子
void init()
{
    int i,j;
    for(i=2 ; i<N ;i++)
    {
        if(!IsNotPrime[i])
        {
            for(j=i ; j<N; j+=i)
            {
                IsNotPrime[j]=1;
                p[j][num[j]++]=i;
            }
        }
    }
}
// 容斥原理，值为q , 当前点（质因子的下标号），树深，
void dfs(int q, int now , int count , LL lcm ,int n)  // [1,n]与q 不互质的数之和
{
    if(count >1)
        lcm=p[q][now]*lcm;
    int k=n/lcm;
    if(count&1)
    {
        ans-=(LL)lcm* k*(k+1)/2;   // 注意一定要强制转换， 因为这个原因ws好几次
    }
    else ans+= (LL)lcm* k*(k+1)/2;
    for(int i=now +1 ; i<num[q] ; i++)
        dfs(q, i , count+1 , lcm , n);
}
LL solve(int n , int q) // 求[1,n]与p不互质的数和
{
    if(n<=0) return 0;
    ans= (LL)n*(n+1)/2;
    for(int i=0 ;i<num[q] ; i++)
        dfs(q,i,1,p[q][i],n);
    return ans;
}
// 容斥原理
int gcd(int a,  int b)
{
    return b==0?a:gcd(b,a%b);
}

int main()
{
    int t,n,q,k,x,y,c;
    LL ret;
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d%d",&n,&q);
        mp.clear();
        while(q--)
        {
            scanf("%d",&k);
            if(k==1)
            {
                scanf("%d%d%d",&x,&y,&c);
                ret=solve(y,c)-solve(x-1,c);
                for(it=mp.begin(); it!=mp.end(); it++)
                {
                    if((*it).first>=x && (*it).first<=y)
                    {
                        if(gcd(c, it->first) == 1) ret-=it->first;
                        if(gcd(c, it->second) ==1)  ret+=it->second;
                    }
                }
                printf("%I64d\n",ret);
            }
            else
            {
                scanf("%d%d",&x,&y);
                mp[x]=y;
            }
        }
    }
    return 0;
}