#include <fstream>
#include <vector>

const int CMAX=1e6;
using namespace std;

ifstream cin ("pinex.in");
ofstream cout ("pinex.out");

char c[CMAX+5];
int p[20];
vector <int> prim;

void ciur()
{
    c[0]=1;
    c[1]=1;
    for(int i=4; i<=CMAX; i+=2)
        c[i]=1;
    for(int i=3; i<=1000; i+=2)
        if(!c[i])
            for(int j=i*i; j<=CMAX; j+=2*i)
                c[j]=1;
    for(int i=2; i<=CMAX; ++i)
        if(!c[i])
            prim.push_back(i);
}

void power2()
{
    p[0]=1;
    for(int i=1; i<=15; ++i)
        p[i]=p[i-1]*2;
}
int main()
{
    ciur();
    power2();
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i){
        long long a,b;
        cin>>a>>b;
        vector <int> decomp;
        long long cop=b;
        long long sol=0;
        for(auto x:prim){
            if(cop<=1)
                break;
            if(cop%x==0){
                while(cop>1 && cop%x==0)
                    cop/=x;
                decomp.push_back(x);
            }
            if(cop==1)
                break;
            if(x*x>=cop){
                decomp.push_back(cop);
                cop=1;
            }
        }
        int subm=(1<<decomp.size())-1;
        for(int masca=0; masca<=subm; ++masca){
            long long newnumber=1;
            int bitcnt=0;
            for(int bit=0; bit<=decomp.size(); ++bit){
                if(masca&p[bit]){
                    bitcnt++;
                    newnumber*=decomp[bit];
                }
            }
            if(bitcnt&1)
                sol-=a/newnumber;
            else
                sol+=a/newnumber;
        }
        cout<<sol<<'\n';
    }
    return 0;
}