#include <bits/stdc++.h>

using namespace std;

const int B = 1e6;

bool c[5 + B];
vector <long long> v;
vector <long long> mu;

void ciur()
{
    for(long long i = 2; i <= B; i++)
    {
        if(c[i] == false)
            for(long long j = i * i; j <= B; j+= i)
                c[j] = true;
    }
    for(long long i = 2; i <= B; i++)
        if(c[i] == false)
            v.push_back(i);
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    ciur();

    long long m, a, b;
    scanf("%lld", &m);

    while(m--)
    {
        scanf("%lld%lld", &a, &b);
        for(long long i = 0; v[i] * v[i] <= b && i < v.size(); i++){
            if(b % v[i] == 0 && v[i] <= b)
                mu.push_back(v[i]);
            while(b % v[i] == 0) b /= v[i];
        }
        if(b > 1) mu.push_back(b);
        long long rez(0);
        for(long long i = 1; i < (1LL << mu.size()); i++){
            long long nr(0), p(1);
            for(long long j = 0; j < mu.size(); j++){
                if(i & (1LL << j)){
                    nr++;
                    p *= mu[j];
                }
            }

            if(nr % 2 == 0) rez -= (a / p);
            else rez += (a / p);
        }

        printf("%lld\n", a - rez);
        mu.clear();
    }
    return 0;
}