#include<bits/stdc++.h>
using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long divi[31],t,a,b;

void duo()
{
    long long d=2,nr=0;;
    while(b>1)
    {
        if(b%d==0)
        {
            divi[++nr]=d;
            while(b%d==0)
                b/=d;

        }
        if(d>sqrt(b)&& b>1)
        {
            divi[++nr]=b;
            b=1;
        }
        if(d==2)
            d++;
        else
            d+=2;
    }
    long long sol=a;
    for(int i=1;i<(1<<nr);++i)
    {
        long long cate=0,prod=1;
        for(int j=0;j<nr;++j)
            if(i&(1<<j))
        {
            prod*=1LL*divi[j+1];
            cate++;
        }
        long long mp;
        if(cate%2)
            mp=-1;
        else
            mp=1;
        sol=sol+1LL*mp*a/prod;
    }
    g<<sol<<'\n';
}

int main()
{
    f>>t;
    for(int i=1;i<=t;++i)
    {
        f>>a>>b;
        duo();
    }
}