#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cmath>
#define pb push_back
#define mp make_pair
#define MAXP 100001
#define INFILE "pinex.in"
#define OUTFILE "pinex.out"
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
long long m,A,B,fact[30];
int fprim[80001];
bitset<MAXP> prim;
void precalc()
{
    prim.flip();
    prim[1]=0;
    for(int i=1;i<MAXP;i++)
        if(prim[i])
        {
            for(int j=i*2;j<MAXP;j+=i)
                prim[j]=0;
            fprim[++fprim[0]]=i;
        }
}
void solve()
{
    long long t=0,d=1,sol=A,nr,prod;
    for(;B>1;d++)
    {
        if(B%fprim[d]==0)
        {
            fact[++t]=fprim[d];
            while(B%fprim[d]==0)
                B/=fprim[d];
        }
        if(fprim[d]>sqrt(B)&&B>1)
        {
            fact[++t]=B;
            B=1;
        }
    }
    for(int i=1;i<(1<<t);i++)
    {
        nr=0;prod=1;
        for(int j=0;j<t;j++)
            if((1<<j)&i)
            {
                nr++;
                prod=1ll*prod*fact[j+1];
            }
        if(nr%2)nr=-1;
        else nr=1;
        sol=sol+1ll*A*nr/prod;
    }
    g<<sol<<'\n';
}
int main()
{
    precalc();
    f>>m;
    for(;m--;)
    {
        f>>A>>B;
        solve();
    }
    f.close();
    g.close();
    return 0;
}