#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cmath>
#define MAXP 1000000
#define INFILE "pinex.in"
#define OUTFILE "pinex.out"
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
long long m,A,B,fact[100];
long long fprim[80001];
bitset<MAXP> prim;
void precalc()
{
    prim.flip();
    prim[0]=prim[1]=0;
    for(int i=2;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=0,sol=A;
    for(;B>1;)
    {
        d++;
        if(B%fprim[d]==0)
        {
            fact[++t]=fprim[d];
            while(B%fprim[d]==0)
                B/=fprim[d];
        }
        if(B>1&&fprim[d]*fprim[d]>B)
        {
            fact[++t]=B;
            B=1;
        }
    }
    for(int i=1;i<(1<<t);i++)
    {
        long long 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;
}