#include <iostream>
#include <fstream>

using namespace std;

const int PMAX = 1000000;

int M;
long long A, B;

unsigned char v[PMAX];

int prim[PMAX / 2];
int np;

long long d[13];
int nd;

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


void factori()
{
    nd = 0;
    for(int i = 1; 1LL * prim[i]*prim[i] <= B; i++)
        if(B % prim[i] == 0)
        {
            d[++nd] = prim[i];
            do
            {
                B /= prim[i];
            }
            while(B % prim[i] == 0);
        }
    if(B > 1)d[++nd] = B;
}


int main()
{
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    ciur();
    f >> M;
    while(M--)
    {
        f >> A >> B;
        factori();
        long long card = 0;
        int nt = 1 << nd;
        for(int i = 1; i < nt; i++)
        {
            int p2, nfact = 0;
            long long prod = 1;
            for(int j = 0; (p2 = 1 << j) <= i; j++)
                if(p2 & i)
                {
                    prod *= d[j + 1];
                    nfact++;
                }
            long long t = A / prod;
            if(nfact % 2 == 0)
                card -= t;
            else
                card += t;
        }
        g << A - card << endl;
    }
    f.close();
    g.close();
    return 0;
}