#include <iostream>
#include<cstdio>
#include<vector>
#define tip long long
using namespace std;
vector<tip> v[20];
tip a,b,i,SOL;
int n,t,j;
int main()
{
   freopen("pinex.in","r",stdin);
   freopen("pinex.out","w",stdout);
   scanf("%d",&t);v[0].push_back(1);
   vector<tip>::iterator it;
   for(;t;t--)
   {
       scanf("%lld%lld",&a,&b);n=0;SOL=a;
       if(b%2==0){v[1].push_back(2);n++;for(;b%2==0;b/=2);}
       for(i=3;i*i<=b;i+=2)
            if(b%i==0)
            {
                for(j=n;j>=0;j--)
                    for(it=v[j].begin();it!=v[j].end();it++)
                        v[j+1].push_back(*it*i);
                while(b%i==0)b/=i;
                n++;
            }
       if(b>1)
       {
           for(j=n;j>=0;j--)for(it=v[j].begin();it!=v[j].end();it++)v[j+1].push_back(*it*b);
           n++;
       }

       for(j=1;j<=n;j+=2)for(;v[j].size();v[j].pop_back())SOL-=a/v[j].back();
       for(j=2;j<=n;j+=2)for(;v[j].size();v[j].pop_back())SOL+=a/v[j].back();
       printf("%lld\n",SOL);

   }
   return 0;
}