#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

bitset<1000001> B;

int w[100];
long long P[300000];
long long x[100];

long long a, b, e, nr, y, sol, k, i, j, p, m;

int main() {
    for (i=2;i<=1000000;i++)
        if (!B[i]) {
            P[++p] = i;
            for (j=i+i;j<=1000000;j+=i)
                B[j] = 1;
        }
    /// P un vector cu cele p numere prime pana la 10^6
    fin>>m;
    for (;m--;) {
        fin>>a>>b;
        e = b;
        k = 0;
        /// aflam factorii primi ai lui b impartind direct
        /// doar la numere prime si cautand pana la radicalul lui b
        for (i=1;P[i]*P[i]<=b && e!=1;i++) {
            if (e%P[i] == 0) {
                x[++k] = P[i];
                while (e%P[i] == 0)
                    e/=P[i];
            }
        }
        /// dupa radical mai poate fi un singur factor prim
        if (e!=1) {
            x[++k] = e;
        }
        /// obtinem x = un vector cu cei k factori primi distincti ai lui b.

        /// mai departe ne intereseaza toate numerele care se pot scrie
        /// ca produs de divizori distincti ai lui b
        /// afisa toate numerele care se pot scrie ca si produs de numere
        /// din x
        /// ex daca k = 3 si x = {2,3,5} vrem sa obtinem
        /// 2, 3, 5, 2*3, 2*5, 3*5, 2*3*5

        /**
        0 0 0
        0 0 1   5
        0 1 0   3
        0 1 1   3*5
        1 0 0   2
        1 0 1   2*5
        1 1 0   2*3
        1 1 1   2*3*5
        **/

        /// generez in w toate submultimile multimii indicilor din x
        /// adica toti vectorii de k componente 0 si 1 si ma intereseaza
        /// elementul din x din dreptul pozitiilor 1.
        memset(w, 0, sizeof(w));
        sol = 0;
        while (!w[0]) {
            j = k;
            while (w[j] == 1) {
                w[j] = 0;
                j--;
            }
            w[j] = 1;
            if (j == 0)
                break;
            nr = 0; /// numar cate elemente are submultimea (pentru semnum +/- al operatiei)
            y = 1;  /// y = produsul
            for (j=1;j<=k;j++) {
                nr+=w[j];
                if (w[j])
                y *= x[j];
            }
            if (nr&1) ///n%2 == 1
                sol += a/y;
            else
                sol -= a/y;
        }
        if (sol > 0)
            fout<<a-sol<<"\n";
        else
            fout<<a+sol<<"\n";
    }

    return 0;
}
/**
ciurul se face o data = val * log val cu (val = 10^6 = radical din b maxim)
in etapa a doua:
    numarul de perechi * (descompunere in factori primi + generare de submultimi pentru factorii primi)
  = numarul de perechi * (supraestimat rad(b) mul mai putin ca impart direct la numerele prime
                          + alg de desc in f primi este 2 ^ k cu k foarte mic 9)
**/