#define Dudica "Dudescu Alexandru"
#include <cstdio>
#include <vector>
#define nmax 1000000001
#define pmax 100000
using namespace std;
FILE *f1=fopen("pinex.in","r"),*f2=fopen("pinex.out","w");
int n,prim[pmax],vf,pb[1000];
long long a,b;
bool p[pmax];
long long pinex(int n,int k)
{
    long nr=0;
    int i,j;
    for(i=1;i<(1<<k);i++)
    {
        long long prod=1;int semn=-1;
        for(j=0;j<k;j++)
        if(i&(1<<j))
        {
            prod*=pb[j];
            semn*=-1;
        }
        nr+=semn*n/prod;
    }
    return nr;
}
int main()
{
    //precalcul
    int i,j;
    p[1]=1;
    for(i=2;i<=pmax;i++)
    if(!p[i])
    {
        prim[vf++]=i;
        for(j=2*i;j<=pmax;j+=i)p[j]=1;
    }
    //
    fscanf(f1,"%d",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(f1,"%d %d",&a,&b);
        int k=0;int vfb=0;
        while(prim[k]<a&&k<vf){if(b%prim[k]==0)pb[vfb++]=prim[k];k++;}
        a=a-pinex(a,vfb);
        for(j=0;j<=vfb;j++)pb[j]=0;
        fprintf(f2,"%lld\n",a);
    }
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.