#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

typedef unsigned long long LL;
const int MAXN = 1000000;

LL A, B;
LL Ans;
bool Prim[MAXN + 10];
LL Fact[40];
int st[40];
vector <LL> Prime;

void Ciur ()
{
    int i, j;

    Prime.push_back (2);
    for (i = 3; i <= MAXN; i += 2){
        if (!Prim[i])
            Prime.push_back (i);

        for (j = i + i; j <= MAXN; j += i)
            Prim[j] = 1;
    }
}

void back (int lev, LL prod)
{
    if (lev & 1)
        Ans += (A / prod);
    else
        Ans -= (A / prod);

    int i;

    for (i = st[lev - 1] + 1; i <= Fact[0]; i ++){
        st[lev] = i;
        if ((unsigned long long) prod * Fact[i] > A)
            continue;
        back (lev + 1, (unsigned long long) 1ULL * prod * Fact[i]);
    }
}

LL Solve ()
{
    int i = 0, j, N, lev;
    LL prod;
    N = Prime.size ();

    while (B > 1 && i < N && (long long) Prime[i] * Prime[i] <= B){
        if (B % Prime[i] == 0){
            Fact[++ Fact[0]] = Prime[i];

            while (B % Prime[i] == 0)
                B /= Prime[i];
        }
        i ++;
    }

    if (B > 1)
        Fact[++ Fact[0]] = B;

    /*long long conf;

    for (conf = 1; conf < (1LL << Fact[0]); conf ++){
        lev = 0;
        prod = 1;

        for (j = 0; j < Fact[0]; j ++)
            if (conf & (1 << j))
                prod *= 1LL * (long long) Fact[j + 1], lev ++;

        if (lev & 1)
            Ans += (A / prod);
        else
            Ans -= (A / prod);
    }*/

    back (1, 1);
    //return 0LL + A - Ans;
    return Ans;
}

int main()
{
    int T;

    Ciur ();
    for (in >> T; T; T --){
        in >> A >> B;
        Ans = 0;
        Fact[0] = 0;
        out << Solve () << "\n";
    }

    return 0;
}