#include <fstream>

using namespace std;
#define MAXP 1000105
#define ll long long

void ciur();
int prim[MAXP], np, nf;
ll fact[20];

int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    ll a, b, prod, rez;
    int nre, cate, n, f, nf, p, p2, i, copi;
    ciur();
    fin>>n;
    while(n--)
    {
        nf = 0;
        fin>>a>>b;
        f = 1;
        rez = 0;
        while(b>1)
        {
            if(prim[f] * prim[f] > b)
            {
                fact[++nf] = b;
                break;
            }
            p = 0;
            while(b%prim[f]==0)
            {
                p++;
                b /= prim[f];
            }
            if(p > 0)
                fact[++nf] = prim[f];
            f++;

        }
        p2 = 1<<nf;
        for(i=1; i<p2; i++)
        {
            copi = i;
            prod = 1;
            nre = 0;
            cate = 0;
            while(copi > 0)
            {
                cate++;
                if(copi & 1)
                {
                    nre++;
                    prod = prod * fact[cate];
                }
                copi>>=1;
            }
            if(nre & 1)
                rez += a/prod;
            else
                rez -= a/prod;
        }
        fout<<a-rez<<'\n';
    }

    return 0;
}
void ciur()
{
    int i, j;
    prim[1] = 2;
    np = 1;
    for(i=3; i*i<MAXP; i+=2)
        if(!prim[i])
        {
            for(j=i*i; j<MAXP; j=j+i+i)
                prim[j] = 1;
            prim[++np] = i;
        }
    for( ; i<MAXP; i+=2)
        if(!prim[i])
            prim[++np] = i;
}