#include <bits/stdc++.h>
#define DIM 1000005
#define ll long long

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

int n, q, k, prim[80005], x[80005];
ll A, B, divi[80005], rez;
bitset <80005> fr;
bitset <DIM> v;

void ciur()
{
    for(int i = 2; i <= 1000000; i++)
        if(!v[i])
        {
            for(int j = i + i; j <= 1000000; j += i)
                v[j] = 1;
            prim[++k] = i;
        }
}

ll calc(int k)
{
    ll prod = 1;
    for(int i = 1; i <= k; i++)
        prod *= divi[x[i]];
    return (A / prod);
}

void bkt(int k)
{
    int a;
    if(k % 2)
        a = 1;
    else
        a = -1;
    for(int i = x[k - 1] + 1; i <= n; i++)
        if(!fr[i])
        {
            fr[i] = 1;
            x[k] = i;
            rez += 1LL * a * calc(k);
            bkt(k + 1);
            fr[i] = 0;
        }
}

int main()
{
    f >> q;
    ciur();

    while(q--)
    {
        f >> A >> B;
        rez = n = 0;
        for(int i = 1; i <= k && prim[i] * prim[i] <= B; i++)
            if(B % prim[i] == 0)
            {
                while(B % prim[i] == 0)
                    B /= prim[i];
                divi[++n] = prim[i];
            }

        if(B > 1)
            divi[++n] = B;
        bkt(1);
        g << A - rez << "\n";
    }

    return 0;
}