#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;
ifstream in("mixperm.in");
ofstream out("mixperm.out");
const int maxd = 1000005;
bitset <maxd> ciur;
vector <int> prime;
vector <int> diviz;

void descompune(int n)
{
    diviz.clear();
    int ind = 0;
    while(1LL * prime[ind] * prime[ind] <= n)
    {
        long long d = prime[ind];
        if(n % d == 0)
        {
            while(n % d == 0)
                n = n / d;
            diviz.push_back(d);
        }
        ind++;
    }
    if(n > 1)
        diviz.push_back(n);
}

void solve()
{
    long long a, b;
    in >> a >> b;
    descompune(b);
    int n = diviz.size();
    long long sol = 0;
    for(int conf = 1; conf < (1 << n); conf++)
    {
        int nrbiti = 0;
        long long prod = 1;
        for(int i = 0; i < n; i++)
        {
            if(conf & (1 << i))
            {
                nrbiti++;
                prod = prod * diviz[i];
            }
        }
        if(nrbiti % 2 == 1)
            sol = sol + a / prod;
        else
            sol = sol - a / prod;
    }
    out << a - sol << "\n";
}

int main()
{
    for(int i = 2; i < maxd; i++)
        ciur[i] = 1;
    for(int i = 2; i < maxd; i++)
        if(ciur[i])
            for(int j = i + i; j < maxd; j = j + i)
                ciur[j] = 0;
    for(int i = 2; i < maxd; i++)
        if(ciur[i])
            prime.push_back(i);
    int m;
    in >> m;
    for(int i = 1; i <= m; i++)
        solve();
    return 0;
}