#include <fstream>
using namespace std;

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

const int MAX = 1000000;
long long nr, M, A, B, fact[30], Prime[79000];
bool EPrim[MAX];

void Ciur (){
    for (int i = 2; i <= MAX; ++ i) {
        if (!EPrim[i]) {
            Prime[++ nr] = i;
            for (int j = 2 ; j <= MAX/i; ++ j) {
                    EPrim[i * j] = true;
            }
        }
    }
}

int Solve () {
    int t = 0;

    while (B > 1) {
        for (int i = 1; i <= nr && Prime[i] * Prime[i] <= B; ++ i) {
            if (B % Prime[i] == 0) {
                fact[++ t] = Prime[i];
                while (B % Prime[i] == 0)
                    B /= Prime[i];
            }
        }

       if (B > 1) {
          fact[++ t] = B;
          B = 1;
       }
    }

    long long sum = A;
    for (int i = 1; i < (1 << t); i++) {
        long long nr = 0, prod = 1;
        for (int j = 0; j < t; j++)
            if ((1 << j) & i) {
                prod *= 1LL * fact[j + 1];
                nr++;
            }

        if (nr % 2) nr = -1;
        else nr = 1;

        sum += 1LL * nr * A / prod;
    }

    out << sum << '\n';

}

int main()
{
    Ciur ();

    in >> M;
    for (int i = 1; i <= M; ++ i) {
        in >> A >> B;
        Solve ();
    }

    return 0;
}