#include <iostream>
#include <fstream>

using namespace std;

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

bool E[1000001];
long long v[100000];
long long nrp, m, n;
long long suma;
long long A, B;
long long diviz[15];///11 e max
int x[15];

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

void afis()
{
    long long p = 1;
    for(int i = 1; i <= m; i++)
        p = 1LL * p * diviz[x[i]];

    if(m % 2 == 0)
        suma -= A / p;
    else suma += A / p;
}

void bt(int k)
{
    if(k <= m)
        for(int i = x[k - 1] + 1; i <= n - m + k; i++)
        {
            x[k] = i;
            bt(k + 1);
        }
    else
        afis();
}

int main()
{
    ciur(1000000);
    int M;
    f >> M;
    for(int i = 1; i <= M; i++)
    {
        suma = 0;
        f >> A >> B;
        int j = 1;
        n = 0;
        while(B > 1)
        {
            if(v[j] == 0)
            {
                n++;
                diviz[n] = B;
                break;
            }
            if(B % v[j] == 0)
            {
                n++;
                diviz[n] = v[j];
                while(B % v[j] == 0)
                    B /= v[j];
            }
            j++;
        }
        for(m = 1; m <= n; m++)
        {
            x[0] = 0;
            bt(1);
        }
        g << A - suma << '\n';
    }
    return 0;
}