#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#define DN 1000005
using namespace std;

bitset<DN> p;
int fact[35];
int pr[100005],sz,sza;

void gen()
{
    for(int i=2;i<DN;++i){

        if(!p[i]){

            for(int j=i+i;j<DN;j+=i)
                p[j]=1;

            pr[++sz]=i;
        }
    }
}

int main()
{
    gen();
    int n;
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    f>>n;

    for(;n;--n)
    {
        fact[0]=0;
        long long a,b;
        long long rez=0;
        f>>a>>b;

        for(int t=1;b!=1 && t<sz;++t)
        {
            int p=0;
            for(; b%pr[t]==0 ;++p,b/=pr[t]);
            if(p)
                fact[++fact[0]]=pr[t];

            if(pr[t]*pr[t] > b && b!=1){

                fact[++fact[0]]=b;
                b=1;
            }
        }
        rez=a;
        for(int i=1;i<(1<<fact[0]);++i)
        {
            int nr=0;
            long long prod=1;
            for(int j=0;j<fact[0];++j)
                if( (1<<j) & i ){

                    prod=prod*1ll*fact[j+1];
                    ++nr;
                }
            if(nr%2) nr=-1;
                else
                    nr=1;
            rez+=nr*1ll*a/prod;
        }
        g<<rez<<"\n";
    }
    return 0;
}