#include <fstream>
#include <cmath>

using namespace std;

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

const int MAX = 1000000;
int m, primfact[MAX], ind, desc[MAX];
bool sieve[MAX + 1];
long long a, b;

void create_sieve(){
    primfact[++ind] = 2;
    for (int i = 4; i <= MAX; i += 2)
        sieve[i] = 1;
    for (int i = 3; i*i <= MAX; i +=2)
        if (!sieve[i]){
            for (int j = i*i; j <= MAX; j += i)
                sieve[j] = 1;
            primfact[++ind] = i;
        }
}

void mia(){
    long long it = 1, fact = 0, sol = a;
    for (; b != 1 && it <= ind; it++){
        if (b % primfact[it] == 0) {
            while (b % primfact[it] == 0)
                b /= primfact[it];
            desc[++fact] = primfact[it];
        }
        if (1LL * primfact[it] * primfact[it] > b)
            break;
    }

    if (b != 1)
        desc[++fact] = b;

    for (int i = 1; i < (1 << fact); i++) {
        long long cnt = 0, prod = 1;
        for (int j = 0; j < fact; j++)
            if ((1 << j) & i) {
                prod = 1LL * prod * desc[j + 1];
                cnt++;
            }
        if (cnt & 1)
            sol -= 1LL * a / prod;
        else sol += 1LL * a / prod;
    }
    fout << sol << '\n';
}

int main()
{
    create_sieve();
    fin >> m;
    for (; m; m--){
        fin >> a >> b;
        mia();
    }
    return 0;
}