#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
#define Fin(file) freopen(file".in","r",stdin)
#define Fout(file) freopen(file".out","w",stdout)
#define Fgen(file) freopen(file".in","w",stdout)
#define Fans(file) freopen(file".ans","w",stdout)
#define int long long
#define div Charlie_Vinnie
using namespace std;

const int N=1e5+5;

int div(int x,int y)
{
    return x>=0 ? x/y : -((-x-1)/y+1);
}

// sum(i=0..n){(a*i+c)/b}
int EuF(int n,int a,int b,int c)
{
    if(n<0) return 0;
    
    if(a==0) return (n+1)*(c/b);
    
    if(a>=b || c>=b){
        return (a/b)*(n*(n+1)/2)+(c/b)*(n+1)+EuF(n,a%b,b,c%b);
    }
    else{
        int m=(a*n+c)/b-1;
        return n*(m+1)-EuF(m,b,a,b-c-1);
    }
}

// allows a,b,c<0, but must n>=0
int exEuF(int n,int a,int b,int c)
{
    if(b<0) { a=-a; b=-b; c=-c; }
    
    int res=0;
    
    if(a<0){
        res-=(-div(a,b))*(n*(n+1)/2);
        a=(a%b+b)%b;
    }
    if(c<0){
        res-=(-div(c,b))*(n+1);
        c=(c%b+b)%b;
    }
    
    return res+EuF(n,a,b,c);
}

// sum(i=l..r){(a*i+c)/b}
int sum(int l,int r,int a,int b,int c)
{
    if(l>0){
        return exEuF(r,a,b,c)-exEuF(l-1,a,b,c);
    }
    else if(r<0){
        return exEuF(-l,-a,b,c)-exEuF(-r-1,-a,b,c);
    }
    else{
        return exEuF(r,a,b,c)+exEuF(-l,-a,b,c)-div(c,b);
    }
}

// num of (u,v) so that t1<ua+vb<=n+t1, t2<ua-vb<=n+t2
int calc(int n,int a,int b,int t1,int t2)
{
    int mid=div(t1-t2,2*b);
    int lt=div(t1-t2-n-1,2*b);
    int rt=div(n+t1-t2,2*b);
    
    return sum(lt+1,mid,b,a,n+t2)-sum(lt+1,mid,-b,a,t1)+sum(mid+1,rt,-b,a,n+t1)-sum(mid+1,rt,b,a,t2);
}

// sum(0<=x<y<n){[a|x+y][b|x-y]}
int work(int n,int a,int b)
{
    int res=0;
    res+=calc(n,a,b,-1,-1);
    if(b%2==0) res+=calc(n,a,b,-b/2-1,b/2-1);
    if(a%2==0) res+=calc(n,a,b,-a/2-1,-a/2-1);
    if((a+b)%2==0) res+=calc(n,a,b,-(a+b)/2-1,(b-a)/2-1);
    // now res = sum(x=0..n-1,y=0..n-1){[a|x+y][b|x-y]}
    if(a%2==0) res-=(n-1)/(a/2)+1;
    else res-=(n-1)/a+1;
    res/=2;
    
    // printf("work(%lld,%lld,%lld)\n",n,a,b);
    
    // int hh=0;
    // For(x,0,n-1) For(y,x+1,n-1) if((x+y)%a==0&&(x-y)%b==0) printf("(%lld,%lld) ",x,y),hh++;
    // assert(res==hh);
    // cout<<"res="<<res<<endl;
    return res;
}

int n,m,ans;
int p[25],w[25],pw[25][45],cnt;

void dfs(int d,int x,int y,int c)
{
    if(d==cnt+1){
        // printf("%cwork(%lld,%lld,%lld)\n",c==1?'+':'-',n,x,y);
        // printf("%c ",c==1?'+':'-');
        ans+=c*work(n,x,y);
        return;
    }
    
    For(i,0,w[d]){
        dfs(d+1,x*pw[d][i],y*pw[d][w[d]-i],c);
        if(i!=w[d]) dfs(d+1,x*pw[d][i+1],y*pw[d][w[d]-i],-c);
    }
}

void solve()
{
    cin>>n>>m;
    
    cnt=0;
    
    int sqm=sqrt(m+0.5),t=m;
    For(i,2,sqm){
        if(t%i==0){
            p[++cnt]=i; w[cnt]=0;
            while(t%i==0) { w[cnt]++; t/=i; }
            pw[cnt][0]=1;
            For(j,1,w[cnt]+1) pw[cnt][j]=pw[cnt][j-1]*p[cnt];
        }
    }
    
    if(t>1){
        p[++cnt]=t; w[cnt]=1;
        pw[cnt][0]=1; pw[cnt][1]=t; pw[cnt][2]=t*t;
    }
    
    ans=0;
    dfs(1,1,1,1);
    cout<<ans<<endl;
    
    // int hh=0;
    // For(x,0,n-1) For(y,x+1,n-1) if((x+y)*(x-y)%m==0) printf("(%lld,%lld)\n",x,y),hh++;
    // printf("std = %lld\n",hh);
}

signed main()
{
    int T;
    cin>>T;
    while(T--) solve();
    
    cerr<<"Time = "<<clock()<<" ms"<<endl;
    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/