//https://www.infoarena.ro/problema/pinex
#include <bits/stdc++.h>

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");
const int MAX_DIVIDERS = 20;
bool divide(long long &x, long long divide){
    if(x % divide != 0)
        return false;
    do{
        x /= divide;
    }while(x % divide == 0);
    return true;
}
void descompunere(long long x, long long v[], int &n){
    n = 0;
    for(long long d = 2; d*d <= x; d++){
        if(divide(x,d))
            v[n++] = d;
    }
    if(x != 1)
        v[n++] = x;
}
void display(long long v[], int n){
    for(int i = 0 ; i <n; i++)
        cout << v[i] << ' ';
    cout << '\n';
}
long long getSol(long long x, long long v[], int n){
    long long ans = 0;
    int full = (1<<n) - 1;
    for(int i = 1 ; i <= full ; i++)
    {
        short int card = 0;
        long long prod = 1;
        for(int j = 0 ; j < n ; j++)
        {
            if(i & (1<<j))
            {
                card++;
                prod *= v[j];
            }
        }
        if(card & 1) ans += x/prod;
        else ans -= x/prod;
    }
    return x - ans;
}
int main()
{  
    long long v[MAX_DIVIDERS], A = 10,B = 5;
    int n, m;
    in >> m;
    for(int i = 0 ; i < m ; i ++){
        in >> A >> B;
        descompunere(B,v,n);
        // display(v,n);
        out << getSol(A,v,n) << '\n';   
    }
    return 0;
}