#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> szita_fuggyveny()
{
    vector<bool>szita(1e6/2+1,true);
    szita[0]=false;
    int i=3;
    int db=0;
    int sz=szita.size();
    int maxim=2*sz-1;
    while(i<=maxim)
    {
        if(szita[i>>1]==true)
        {
            db++;
            int j=i+i+i;
            while(j<=maxim)
            {
                szita[j>>1]=false;
                j+=i+i;
            }
        }
        i+=2;
    }
    vector<int>prim(db+1);
    prim[0]=2;
    int j=1;
    for(int i=3;(i>>1)<sz;i+=2)
        if(szita[i>>1])
            prim[j++]=i;
    return prim;

}

vector<long long> prim_teny(long long b,const vector<int>&prim)
{
    int i=0;
    vector<long long>v;
    long long x=prim.size();
    while(b>1 && i<x)
    {
        int d=prim[i];
        if(b%d==0){
            while(b%d==0)
            {
                b/=d;
            }
            v.push_back(d);
        }
        i++;
    }
    if(b>1)
        v.push_back(b);
    return v;
}

long long solve(long long a,long long b,const vector<int>&prim)
{
    auto v=prim_teny(b,prim);
    long long db=0;
    int sizev=v.size();
    for(size_t i=1;i<(1<<sizev);i++)
    {
        int cnt=0;
        long long prod=1;
        for(int j=0;j<sizev;j++)
            if((1ll<<j)&i){
                ++cnt;
                prod*=v[j];
            }
        if(cnt%2)db+=a/prod;
        else db-=a/prod;
    }
    return a-db;
}

int main()
{
    ifstream be("pinex.in");
    ofstream ki("pinex.out");
    int n;
    be>>n;
    auto prim=szita_fuggyveny();
    for(int i=0;i<n;i++)
    {
        long long a,b;
        be>>a>>b;
        ki<<solve(a,b,prim)<<endl;
    }
    return 0;
}