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

using namespace std;

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

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