#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long t, a, b, k, x, nr, sol, p[1000001], v[101];
int ciur[1000001];
int main() {
    ///o sa calculez nr de numere mai mici sau egale cu A si care nu sunt prime cu B si dupa scad
    ///daca avem d1, d2, .., dk divizorii orimi ai lui B. Orice nr x neprim cu B va fi divizibil cu unul din d1, d2, ..., dk
    ///de aici rezulta ca vom avea k multimi formate din numerele naturale mai mici ca A si prime cu cate unul din d1, d2, dk
    ///valoarea cautata este cardinalul reuniunii lor si folosim pinex
    ///avem urmatorii pasi
    ///1. calculam divizorii primi ai lui B(o eventuala optimizare ar fi sa precalculam cu un ciur primele 10^6 nr prime)
    ///2. Generam toate submultimile de divizori primi
    ///3. Pentru multimea {x1, x2, ..., xi}, adunam intersectia [A\(x1*x2*...*xi)] daca i e par, si scadem daca i e impar
    k=0;
    ciur[0]=1;
    ciur[1]=1;
    for(int i=2; i<=1000000; i++)
    {
        if(ciur[i]==0)
        {
            p[++k]=i;
            for(int j=2*i; j<=1000000; j+=i)
            {
                ciur[j]=1;
            }
        }
    }
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        x=b;
        k=0;
        for(int i=1; p[i]*p[i]<=b && x!=1; i++)
        {
            if(x%p[i]==0)
            {
                v[++k]=p[i];
                while(x%p[i]==0)
                {
                    x=x/p[i];
                }
            }
        }
        if(x!=1)
        {
            v[++k]=x;
        }
        sol=0;
        for(int i=1; i<(1<<k); i++)
        {
            nr=0;
            x=1;
            for(int j=0; j<k; j++)
            {
                if((1<<j)&i)
                {
                    x*=v[j+1];
                    nr++;
                }
            }
            if(nr%2==1)
            {
                sol-=a/x;
            }
            else
            {
                sol+=a/x;
            }
        }
        if(sol>0)
        {
            fout<<a-sol<<"\n";
        }
        else{
            fout<<a+sol<<"\n";
        }
    }
    return 0;
}