#include <iostream>
#include <fstream>

using namespace std;

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

int v[1000000], nrp, m, n;
long long suma;
long long A, B;
long long div[13];///11 e max
int x[15];

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

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

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

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

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(B % v[j] == 0)
            {
                div[++n] = v[j];
                while(B % v[j] == 0)
                    B /= v[j];
            }
            j++;
        }
        for(int m = 1; m <= n; m++)
        {
            x[0] = 0;
            bt(1, n, m);
        }

        g << A - suma << '\n';
    }
    return 0;
}