#include <bits/stdc++.h>
using namespace std;

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

int m;
long long a,b;
vector < long long > primes;
bool is_prime[1000005];
vector < long long > divisors;
long long total;

void ciur() {
    primes.push_back(2);
    for (long long i=3;i<=1000001;i+=2) {
        if (!is_prime[i]) {
            primes.push_back(i);
            for (long long j=i*i;j<=1000001;j+=i) {
                is_prime[j]=1;
            }
        }
    }
}

void bkt(long long prod, int nr_elem, int pos) {
    if (nr_elem%2) {
        total += a/prod;
    }
    else {
        total -= a/prod;
    }
    for (int i=pos+1;i<divisors.size();i++) {
        if (a/prod>divisors[i]) {
            bkt(prod*divisors[i],nr_elem+1,i);
        }
    }
}

void solve() {
    f >> a >> b;
    divisors.clear(); total=0;
    for (long long k:primes) {
        if (b%k==0) {
            while (b%k==0) {
                b /= k;
            }
            divisors.push_back(k);
        }
    }
    if (b!=1) {
        divisors.push_back(b);
    }
    for (int i=0;i<divisors.size();i++) {
        bkt(divisors[i],1,i);
    }
    g << a-total << '\n';
}

int main()
{
    ciur();
    f >> m;
    while (m--) {
        solve();
    }
    return 0;
}