#include <iostream>
#include <cstdio>
#include <vector>
#define maxp 1000000
#include <cstring>
#include <bits/stdc++.h>
using namespace std;

int m,k;
long long a,b;
int diviz[maxp],fprim[80005];
bool prim[maxp];

void generare()
{
    for (int i=2; i<=maxp; i++)
    {
        if (prim[i]==0)
        {
            for (int j=i; j<=maxp; j+=i)
                prim[j]=1;
            diviz[++k]=i;
        }
    }
}
void solve(int a,int b)
{
    long long total=a;
    fprim[0]=0;

    for (int i=1; i<=k && diviz[i]*diviz[i]<=b; ++i)
    {
        if (b==1)
            break;

        if (b%diviz[i]==0)
            {
                fprim[++fprim[0]]=diviz[i];
                while (b%diviz[i]==0)
                    b/=diviz[i];
            }
    }

    for (int i=1; i <=(1 << fprim[0])-1 ; ++i) ///mergi pana la 2 la nr de divizori -1
    {
        long long t=1;
        int nr=0;
        for (int j=0; j < fprim[0]; ++j)
            if (i & (1<<j)) ///daca 2 la j e in componenta binara a lui i
            {
                ++nr; ///cresc nr de 1
                t*=fprim[j+1]; ///il inmultesc la t
            }
        if (nr%2==1)
            total-=a/t;
        else
            total+=a/t;
    }
    printf("%lld\n",total);
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&m);
    generare();
    for (int i=1; i<=m; ++i)
    {
        scanf("%lld%lld",&a,&b);
        solve(a,b);
    }
    return 0;
}