#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");

vector <int> v;

long long neprime(long long a,long long b)
{
    int d=2;
    long long rez=0;
    while(b!=1&&d<=a)
    {
        long long e=0;
        while(b%d==0)
        {
            b/=d;
            e++;
        }
        if(e!=0) ///divizor prim
            v.push_back(d);
        if(d==2)
            d++;
        else
            d+=2;
        if(d*d>b&&b!=1)
        {
            v.push_back(b);
            b=1;
        }
    }
    int n=v.size();
    for(int i=1;i<(1<<n);i++)
    {
        long long prod=1,nr=0;
        for(int j=0;j<n;j++) //parcurgem vectorul cu divizorii primi ai lui b
            if((1<<j)&i) // verif daca bitul j este marcat in i
            {
                prod=prod*v[j];
                nr++;
            }
        if(nr%2==0)
            rez=rez-a/prod;
        else
            rez=rez+a/prod;
    }
    v.clear();
    return rez;

}

int main()
{
    long long a,b;
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        cout<<a-neprime(a,b)<<'\n';
    }
    return 0;
}