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

#define ll long long

int T, K, Conf;
ll A, B, V[100], i;

int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    cin >> T;
    for(; T; T --)
    {
        cin >> A >> B;
        K = 0;
        for(i = 2; i * i <= B; i++)
            if(B % i == 0)
            {
                V[K ++] = i;
                while(B % i == 0) B /= 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;
}