#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<bitset>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

int const NMax = 1000000;
bitset <2*NMax> B;
vector <int> Ciur;
vector <long long> Div;
long long a, b, m;

void Precalc()
{
    long long i, j;
    for(i=2; i<=NMax; i++)
        if(!B[i]){
            Ciur.push_back(i);
            for(j=i*i; j<=NMax; j+=i)
                B[j] = 1;
        }
}

void Read()
{
    f>>a>>b;
}

void Solve()
{
    int rad, nrdiv, i, j;
    long long sol = 0, prod, card;
    Div.clear();

    rad = sqrt(b);
    for(i=0; Ciur[i] <= rad; i++)
        if(b % Ciur[i] == 0){
            Div.push_back(Ciur[i]);
            while(b % Ciur[i] == 0)
                b /= Ciur[i];
        }
    if(b>1){
        Div.push_back(b);
        b = 0;
    }

    nrdiv = Div.size();
    for(i=1; i<(1<<nrdiv); i++){
        prod = 1;
        card = 0;
        for(j=0; j<nrdiv; j++)
            if(i & (1<<j)){
                card++;
                prod *= Div[j];
            }
        if(card % 2 == 1)
            sol += a/prod;
        if(card % 2 == 0)
            sol -= a/prod;
    }

    g<<a - sol<<"\n";
}

int main()
{
    f>>m;
    Precalc();
    while(m--){
        Read();
        Solve();
    }
    return 0;
}