#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;
    for(int i=3;i*i<=B_MAX;i+=2)
        if( prime[i] )
        {
            for(int j=i*i;j<=B_MAX;j+=2*i)
                prime[j]=0;
        }
    for(int i=2;i<=B_MAX;i++)   /// adaugarea trebuie facuta separat pt a nu sari
        if( prime[i] )          /// elemente
            lista_prime.push_back(i);
    for(auto w:lista_prime)cout << w << " ";
}

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;
    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;
}