#include <bits/stdc++.h>

#define int long long

using namespace std;

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

/// dându-se două numere naturale A şi B, să se determine numărul de numere naturale mai mici sau egale cu A şi prime cu B
/// idee : din toate numerele de la 1 la A, trebuie sa le calculez pe cele care sunt neprime cu B, adica sa aiba un divizor comun cu B
/// astfel trebuie sa aflu toate numerele prime mai mici decat B, care sunt divizori ai lui B
/// si apoi pinex cu toti multiplii acestor numere prime

int q, a, b;
bool prim[100100];
int nrPrime[100100];
int cntPrime;

void ciur()
{
    for(int i = 1; i <= 100000; i ++)
    {
        prim[i] = true;
    }
    prim[1] = false;
    for(int i = 4; i <= 100000; i += 2)
    {
        prim[i] = false;
    }
    for(int i = 3; i * i <= 100000; i += 2)
    {
        if(prim[i] == true)
        {
            for(int j = i * i; j <= 100000; j += 2 * i)
            {
                prim[j] = false;
            }
        }
    }
}

signed main()
{
    ciur();
    fin >> q;
    while(q--)
    {
        fin >> a >> b;
        cntPrime = 0;
        for(int i = 2; i * i <= b; i ++)
        {
            if(prim[i] == true && b % i == 0)
            {
                nrPrime[++cntPrime] = i;
            }
        }
        for(int i = 1; i <= cntPrime; i ++)
        {
            while(b % nrPrime[i] == 0)
            {
                b /= nrPrime[i];
            }
        }
        if(b > 1)
        {
            nrPrime[++cntPrime] = b;
        }
        int answer = 0;
        for(int i = 1; i < (1 << cntPrime); i ++)
        {
            int nr = 0;
            int val = 0;
            int creeazaNr = 1;
            for(int j = 0; j < cntPrime; j ++)
            {
                if(i & (1 << j))
                {
                    nr++;
                    creeazaNr *= nrPrime[j + 1];
                }
            }
            val += a / creeazaNr;
            if(nr % 2 == 1)
            {
                answer += val;
            }
            else
            {
                answer -= val;
            }
        }
        answer = a - answer;
        fout << answer << '\n';
    }
}