/*
    Keep It Simple!
*/
 
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
 
#include<cstdio>
 
long long C[80000], NrDiv, Div[80000];
bool viz[1000001];
long long T, A, B;
 
void Ciur()
{
    C[NrDiv++] = 2;
    for (int i = 3; i <= 1000001; i+=2)
    if (!viz[i])
    {
        C[NrDiv++] = i;
        for (int j = i; j <= 1000001; j+=i)
            viz[j] = 1;
    }
}
 
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    Ciur();
    scanf("%lld", &T);
    while (T--)
    {
        scanf("%lld%lld", &A, &B);
        long long NrDivB = 0;
        for (int i = 0; i < NrDiv && C[i] * C[i] < B; i++)
        {
            if (B%C[i] == 0)
            {
                Div[NrDivB++] = C[i];
                while (B%C[i] == 0) { B /= C[i]; }
            }
        }
        if (B > 1) Div[NrDivB++] = B;
        long long sign = 0, Final = 0, Jos = 1;
        for (int i = 1; i < (1 << NrDivB); i++)
        {
            sign = 0,Jos = 1;
            for (int j = 0; j < NrDivB;j++)
            if (i&(1<<j))
                Jos *= Div[j] , sign++;
            if (sign&1)
                Final += A / Jos;
            else
                Final -= A / Jos;
        }
        printf("%lld\n", A-Final);
    }
     
    return 0;
     
}