#include <fstream>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

typedef unsigned long long mare;
mare qa, qb;

int v[100001];
bool b[1000001];
mare d[51];
mare t;
int ind[51], l;

mare calc()
{
    int i;
    mare rez = 1;
    for (i = 1; i<=l; i++)
    {
        if (d[ind[i]] <= qa / rez)
            rez = rez * d[ind[i]];
        else
            return 0;
    }
    return qa/rez;
}

void bkt(int p)
{
    if (p == l+1)
        t = t + calc();
    else
    {
        int i;
        for (i = ind[p-1]+1; i<=d[0]; i++)
        {
            ind[p] = i;
            bkt(p+1);
        }
    }
}

int main()
{
    int q, i, j;
    mare nr;
    b[0] = b[1] = 1;
    for (i = 2; i<=1000; i++)
        if (b[i] == 0)
            for (j = i*i; j<=1000000; j = j+i)
                b[j] = 1;
    int k = 1;
    v[1] = 2;
    for (i = 3; i<=1000000; i=i+2)
        if (b[i] == 0)
        {
            k++;
            v[k] = i;
        }
    fin >> q;
    for (i = 1; i<=q; i++)
    {
        fin >> qa >> qb;
        d[0] = 0;
        j = 1;
        while (1ull*v[j] * v[j] <= qb)
        {
            if (qb%v[j] == 0)
            {
                d[0]++;
                d[d[0]] = v[j];
                while (qb%v[j] == 0)
                    qb = qb/v[j];
            }
            j++;
        }
        if (qb > 1)
            d[++d[0]] = qb;
        nr = 0;
        for (l = 1; l<=d[0]; l++)
        {
            t = 0;
            bkt(1);
            if (l%2 == 1)
                nr = nr + t;
            else
                nr = nr - t;
        }
        fout << qa - nr << '\n';
    }
    return 0;
}