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

using namespace std;

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

int n;

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);
}

int solve(int a, int b)
{
    //calc div b
    vector<int> div;
    int sq = sqrt(b);
    for(int i=2; i<=sq && b>1; i++)
    {
        if(b%i == 0)
        {
            div.push_back(i);
            while(b%i == 0) b/=i;
        }
    }
    if(b>1) div.push_back(b);
    return bkt(div,0,a,1,1);
}

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