/// Cerinta
/*
Principiul includerii si excluderii

Aplicaţie
Răspundeţi la M întrebări de tipul: „ 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 ”. Două numere naturale x, y sunt prime între ele dacă cmmdc(x, y) = 1.

Notaţii
În loc să calculăm în mod direct numărul de numere mai mici ca A şi prime cu B, va fi mai uşor să calculăm numărul de numere mai mici ca A şi neprime cu B, după care să scădem acest rezultat din A. Astfel, vom lua în considerare divizorii primi ai lui B; fie aceştia d1, d2 ... dk. Este evident că orice număr natural x pentru care cmmdc(x, B) ≠ 1 va fi divizibil cu unul din numerele d1, d2 ... dk. De aici rezultă că vom avea k mulţimi formate din numerele naturale mai mici ca A şi prime cu câte unul din divizorii primi ai lui B. Valoarea căutată este reprezentată de cardinalul reuniunii lor. Calcularea acestui cardinal implică principiul includerii şi exlcuderii.

Date de intrare
Fişierul de intrare pinex.in va conţine pe prima linie numărul M, reprezentând numărul de întrebări. Următoarele M linii vor conţine câte două numere A şi B cu semnificaţia din enunţ.

Date de ieşire
Fişierul de ieşire pinex.out va conţine M linii, pe linia i fiind răspunsul la a i-a întrebare.

Restricţii
1 ≤ M ≤ 500.
1 ≤ A ≤ 1018.
1 ≤ B ≤ 1012.
Pentru 30% din teste M ≤ 100 şi A, B ≤ 1 000.
Pentru 70% din teste A, B ≤ 109.
*/

/// Rezolvare
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1000005

using namespace std;

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


bitset < MAX > nonprim;
vector < ll > Prim, v;
ll a, R, r;
int n;

void ciur()
{
    int i, j;

    nonprim[0] = nonprim[1] = 1;
    for(i = 4; i < MAX; i += 2 ) nonprim[i] = 1;
    for(i = 3; i * i < MAX; i += 2) if(nonprim[i] == 0)
        for(j = i * i; j < MAX; j += i + i) nonprim[j] = 1;

    Prim.pb(2);
    for(i = 3; i <= MAX; i += 2) if(nonprim[i] == 0) Prim.pb(i);
}

void bkt(int nr, int k, int last)
{
    int i;

    if(k == nr + 1)
    {
        if(nr % 2 == 1) R += a / r;
        else R -= a / r;
    }
    else
    {
        for(i = last + 1; i < n; i++)
        {
            r *= v[i];
            bkt(nr, k + 1, i);
            r /= v[i];
        }
    }
}

int main()
{
    ll b;
    int TT, i;

    ciur();

    fin >> TT;
    while(TT--)
    {
        v.clear();
        fin >> a >> b;

        i = 0;
        while(Prim[i] * Prim[i] <= b)
        {
            if(b % Prim[i] == 0)
            {
                v.pb(Prim[i]);
                while(b % Prim[i] == 0) b /= Prim[i];
            }
            i++;
        }

        if(b != 1) v.pb(b);

        R = 0, n = v.size();
        for(i = 1; i <= n; i++)
        {
            r = 1;
            bkt(i, 1, -1);
        }

        fout << a - R << '\n';
    }


    return 0;
}

/// Exemple
/*
IN:
3
10 5
20 6
50 30


OUT:
8
7
14
*/