#include <iostream>
#include <fstream>
using namespace std;

#define ll long long
#define Nmax 1000010

bool Prime[Nmax];
int T, K, Conf, LimPrime;
ll A, B, V[100], P[80010], i, j;

int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    cin >> T;
    for(i = 2; i < Nmax; i++) Prime[i] = 1;
    for(i = 2; i < Nmax; i++)
        if(Prime[i])
        {
            P[++LimPrime] = i;
            for(j = 2 * i; j < Nmax; j += i) Prime[j] = 0;
        }
    for(; T; T --)
    {
        cin >> A >> B;
        K = 0;
        for(i = 1; i < LimPrime && P[i] * P[i] <= B; i ++)
            if(B % P[i] == 0)
            {
                V[K ++] = P[i];
                while(B % P[i] == 0) B /= P[i];
            }
        if(B > 1) V[K ++] = B;
        ll Ans = 0;
        for(Conf = 1; Conf < (1 << K); Conf ++)
        {
            int NumberSign = 0;
            ll CurrentProd = 1;
            for(i = 0; i < K; i++)
                if(Conf & (1 << i))
                    NumberSign ++, CurrentProd *= V[i];
            if(NumberSign % 2 == 0) CurrentProd = -CurrentProd;
            Ans += A / CurrentProd;
        }
        cout << A - Ans << "\n";
    }
    return 0;
}