#include <iostream>
#include <fstream>
#define maxn 1000010
using namespace std;
ifstream in ("pinex.in");
ofstream out("pinex.out");

bool c[maxn];
int prime[maxn],ct;
void ciur()
{
    int i,j;
    c[0]=1;
    c[1]=1;

    for(i=3;i*i<maxn;i+=2)
        if(c[i]==0)
            for(j=i*i;j<maxn;j=j+2*i)
                c[j]=1;
prime[++ct]=2;
      for(i=3;i<maxn;i+=2)
        if(c[i]==0)
            prime[++ct]=i;
}


void solve(long long a, long long b)
{
    int sol;
    int div[20],j=1,i;
    for(i=1;i<=ct&&prime[i]*prime[i]<=b&&b>1;i++)
        if(b%prime[i]==0)
        {
            while(b%prime[i]==0)
                b=b/prime[i];
            div[j]=prime[i];
            ++j;

        }
        if(b>1)
            div[j++]=b;



        int it;

    int lev,prod,k;
    for (it = 1; it < (1LL << (j-1)); it ++){
        lev = 0;
        prod = 1;

        for (k = 0; k < j-1; k ++)
            if (it & (1 << k))
                prod *= 1LL * (long long) div[k+1], lev ++;

        if (lev & 1)
            sol+=(a / prod);
        else
            sol-=(a / prod);
    }

sol=a-sol;
    out<<sol<<"\n";
}


int main()
{
    int t;
    long long a,b;
    in>>t;
    ciur();
    while(t--)
    {
        in>>a>>b;
        solve(a,b);
    }
    return 0;
}