#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 * 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]<= b && i < v.size(); i++)
            if(b % v[i] == 0)
                mu.push_back(v[i]);

        long long rez(0);
        for(long long i = 1; i < (1 << mu.size()); i++){
            long long nr(0), p(1);
            for(long long j = 0; j < mu.size(); j++){
                if(i & (1 << 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;
}