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

using namespace std;



vector<int> prim_teny(long long a,long long b)
{
    int d=2;
    vector<int>v;
    while(b>1)
    {
        if(b%d==0){
            while(b%d==0)
            {
                b/=d;
            }
            v.push_back(d);
        }
        d++;
    }
    return v;
}

long long solve(long long a,long long b)
{
    auto v=prim_teny(a,b);
    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+=1LL *a/prod;
        else db-=1LL *a/prod;
    }
    return a-db;
}

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