#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

vector<long long int> v[500000];



void pre_calc(){
    for(long long int B=1;B<500000;++B){
        vector<long long int> factors;
        long long int b=B;
        long long int i=2;
        while (i*i <= b){
            if(b%i == 0){
                factors.push_back(i);
                while(b%i == 0)b/=i;
            }

            i+=1;
        }
        if(b > 1)factors.push_back(b);

        v[B]=factors;
    }
}

long long int solve(long long int& a, long long int& b){
    vector<long long int> factors;

    if(b<500000)factors=v[b];
    else{
        long long int i =2;
        while (i*i <= b){
            if(b%i == 0){
                factors.push_back(i);
                while(b%i == 0)b/=i;
            }

            i+=1;
        }
        if(b > 1)factors.push_back(b);
    }

    int n = factors.size();
    int mini = 1, maxi = (1<<n)-1;

    long long int sum = 0;

    for(int c=mini; c<=maxi; ++c){
        long long int prod = 1;
        int nr=0;

        for(int j = 0; j<n; ++j){
            if((1<<j)&c){
                prod*=factors[j];
                nr+=1;
            }
        }



        long long int rez = a/prod;
        if (nr%2==0)rez = -rez;

        //cout<<prod<<" "<<nr<<" "<<rez<<"\n";

        sum += rez;
    }

    return a-sum;
}

int main()
{
    pre_calc();
    int m;
    long long int a, b;
    fin>>m;
    for(int i=1; i<=m; ++i){
        fin>>a>>b;
        fout<<solve(a, b)<<"\n";
    }
    return 0;
}