#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LIM 1000001

int pr[80000],n,fact[20];
bool x[20];
long long a,b;

void ciur(){
    int i=2,nr = 0;
    bool p[LIM];
    memset(p,0,sizeof(p));
    while(i<=1000)
    {
        while(p[i])i++;
        for(int j=i*i;j<LIM;j+=i)p[j]=1;
        i++;
    }
    for(int i=2;i<LIM;i++)
    if(p[i]==0)pr[++nr]=i;
}

void desc(){
    int i=1;
    while(b>1 && pr[i]*pr[i]<=b)
    {
        if(b%pr[i]==0)
        {
            while(b%pr[i]==0)b/=pr[i];
            fact[++n]=pr[i];
        }
        i++;
    }
    if(b!=1)fact[++n]=b;
}

void solve()
{
    long long s = 0, r = 1;
    int bit = 0,i;
    n = 0;
    desc();
    memset(x,0,sizeof(x));
    while(x[n+1]==0)
    {
        i=1;
        while(x[i]){ bit--; x[i]=0; r/=fact[i]; i++; }
        x[i]=1; r*=fact[i]; bit++;
        if(x[n+1]==0)
        if(bit%2==1)s+=a/r; else s-=a/r;
    }
    printf("%lld\n",a-s);
}

int main(){
    int t;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    ciur();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld %lld",&a,&b);
            //printf("%d %d\n",a,b);
            solve();
        }
    return 0;
}