#include <cstdio>

using namespace std;

long long a,b;
long long fac[80000];
long long facb[50];

void ciur()
{
    fac[0] = 2;
    fac[1] = 2;
    fac[2] = 3;

    bool ok;

    for(long long i = 5; i <= 1000000; i += 2)
    {
        ok = true;
        for(int j = 1; ok && j <= fac[0] && fac[j] * fac[j] <= i; ++j)
            if(i % fac[j] == 0)
                ok = false;

        if(ok)
            fac[++fac[0]] = i;
    }
}

void factori_b()
{
    facb[0] = 0;
    for(int i = 1; i <= fac[0]; ++i)
        if(b % fac[i] == 0)
        {
            facb[++facb[0]] = fac[i];

            while(b % fac[i] == 0)
                b /= fac[i];
        }
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    ciur();

    int teste;
    scanf("%d", &teste);

    for(int i = 1; i <= teste; ++i)
    {
        scanf("%lld %lld", &a, &b);
        factori_b();

        long long total = a;

        for(long long p = 1; p < (1 << facb[0]); ++p)
        {
            long long t = 1, nr = 0;

            for(int k = 0; k < facb[0]; ++k)
                if(p & (1 << k))
                {
                    ++ nr;
                    t *= facb[k+1];
                }

                if(nr % 2 == 1)
                    total -= a / t;
                else
                    total += a / t;
        }

        printf("%lld\n", total);
    }

    return 0;
}