#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int nmax = 1e6+12;
int n;
bool ciur[nmax];
vector<int>primes;

int bkt(vector<int> div, int i, int a, int fact, int semn)
{
    if(i == div.size())
    {
        return semn * a / fact;
    }
    return bkt(div,i+1,a,fact,semn) + bkt(div,i+1,a,fact*div[i],-semn);
}

void erat()
{
    for(int i=2; i<nmax; i++)
    {
        if(ciur[i] == 0)
        {
            primes.push_back(i);
            for(int j = i*i; j<nmax; j+=i)
                ciur[j] = 1;
        }
    }
}

int solve(int a, int b)
{
    //calc div b
    vector<int> div;
    for(auto p:primes)
    {
        if(b%p == 0)
        {
            div.push_back(p);
            while(b%p == 0) b/=p;
        }
    }
    if(b>1) div.push_back(b);
    return bkt(div,0,a,1,1);
}

int32_t main()
{
    erat();
    int t; fin>>t;
    while(t--)
    {
        int a,b;
        fin>>a>>b;
        fout<<solve(a,b)<<"\n";
    }
    return 0;
}