#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");ofstream fout("pinex.out");

const int B_MAX = 1e6;

vector<int> lista_prime; /// index 0

void Generare_Ciur()
{
    bitset< B_MAX+3 > prime;
    for(int i=2;i<=B_MAX;i++)
        prime[i]=1;
    lista_prime.push_back(2);
    for(int i=3;i<=B_MAX;i+=2)/// optimizeaza asta!
        if( prime[i] )
        {
            lista_prime.push_back(i);
            for(int j=3*i;j<=B_MAX;j+=2*i)/// optimizeaza asta!
                prime[j]=0;
        }
//    for(auto w:lista_prime)cout << w << " ";
} /// optimizeaza asta!

int div_b[40],ct_div;

void Rezolvare()
{
    long long a,b;
    fin >> a >>b;
    ct_div=0;
    for( auto w:lista_prime )
        if( b%w==0 )
        {
            div_b[ ++ct_div ]=w;
            while( b%w==0 )
                b/=w;
        }
//    if( b!=1 )
//        div_b[ ++ct_div ]=b; /// <---- opinion ? pare util
    long long ans=0;
    for(int i=1;i<= (1<<ct_div)-1;i++ )
    {
        int nr_folositi=0;
        long long val=1;
        for(int j=0; (1<<j)<=i ;j++ )
            if( 1<<j & i )
            {
                nr_folositi++;
                val*=div_b[ j+1 ];
            }

        int semn=-1;
        if( nr_folositi&1 )
            semn=1;
        ans+= semn*a/val;
    }
    fout << a-ans <<"\n";
}

int main()
{
    int q;
    fin >> q;
    Generare_Ciur();
    for(int i=1;i<=q;i++)
        Rezolvare();
    return 0;
}