#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

int cnt = 0, N;
long long R, A;
int Index_Prime[10000];
bitset <1000005> Ciur;
vector <int> v;

void Recurs (int depth, int depth_initial, long long Prod, int ind) {
    if (!depth)
    {
        R += 1LL * (depth_initial & 1 ? 1 : -1) * (A / Prod);
        return;
    }
    for (++ind; ind < N; ind++)
    {
        if (ind + depth > N) return;
        Recurs (depth - 1, depth_initial, Prod * v[ind], ind);
    }
}

long long Business (long long A, long long B) {
    v.clear ();
    for (int i = 0; 1LL * Index_Prime[i] * Index_Prime[i] <= B; i++)
    {
        if (B % Index_Prime[i] == 0)
        {
            v.push_back (Index_Prime[i]);
            while (B % Index_Prime[i] == 0) B /= Index_Prime[i];
        }
    }
    if (B > 1) v.push_back (B);
    N = v.size ();
    R = 0;
    for (int depth = 1; depth <= N; depth++)
    {
        Recurs (depth, depth, 1, -1);
    }
    return A - R;
}

void Initializare_Prime () {
    Index_Prime[0] = 2;
    for (int i = 3; i <= 99999; i += 2)
    {
        if (!Ciur[i])
        {
            Index_Prime[++cnt] = i;
            for (int j = i << 1; j <= 99999; j += i)
                Ciur[j] = 1;
        }
    }
}

int main () {
    Initializare_Prime ();
    ifstream fin ("pinex.in");
    ofstream fout ("pinex.out");
    int M;
    long long B;
    fin >> M;
    for (int i = 0; i < M; i++)
    {
        fin >> A >> B;
        fout << Business (A, B) << "\n";
    }
    fin.close ();
    fout.close ();
    return 0;
}