#include <bits/stdc++.h>

using namespace std;

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

int t;
int a,b;
int divA[20],nr;

int main()
{
    in>>t;

    while(t--)
    {
        in>>b>>a;
        nr=0;

        int rad=sqrt(a);
        for(int i=2;i<=rad && a!=1;i++)
            if(a%i==0)
            {
                divA[++nr]=i;

                while(a%i==0)
                    a/=i;
            }

        if(a>1)
            divA[++nr]=a;

        int fin=1<<nr;
        int nrI,divr,sum=b;

        for(int i=1;i<=fin-1;i++)
        {
            nrI=0;
            divr=1;

            for(int j=0;j<nr;j++)
                if( i&(1<<j) )
                {
                    nrI++;
                    divr*=divA[j+1];
                }

            if(nrI%2 == 0)
                sum+=b/divr;
            else
                sum-=b/divr;
        }

        out<<sum<<'\n';
    }

    return 0;
}