#include<fstream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
#define ll long long
#define MAX_P 1000000
ll M,A,B,fact[30];
int fprim[80000];
bool prim[MAX_P];
void prec()
{
    fill(prim+2,prim+MAX_P,1);
    for(int i=2;i<MAX_P;i++)
      if(prim[i])
      {
          for(int j=2*i;j<MAX_P;j+=i)
            prim[j]=false;
          fprim[++fprim[0]] = i;
      }
}
void solve()
{
    ll t=0,d=0;
    while(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;
        }
    }
    ll sol= A;
    for(int i=1;i<(1<<t);i++)
    {
        ll nr=0,prod=1;
        for(int j=0;j<t;j++)
          if((1<<j)&i)
          {
              prod=1LL*prod*fact[j+1];
              nr++;
          }
        if(nr%2)
          nr=-1;
        else
          nr=1;
        sol=sol+1LL*nr*A/prod;
    }
    g<<sol<<"\n";
}
int main()
{
    prec();
    f>>M;
    for(int i=1;i<=M;i++)
    {
        f>>A>>B;
        solve();
    }
    return 0;
}