/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 9, 2010, 4:30 PM
 */
#include <vector>
#include <fstream>
#define N 1000000
#define Nmax N/16+1

/*
 *
 */
using namespace std;
typedef long long int lld;
vector< int > dvi1, dvi1B;
inline lld next_nbits( lld x )
{
    lld smallest, new_smallest, ripple, one;
    smallest=( x & -x );
    ripple=x+smallest;
    new_smallest=( ripple & -ripple );
    one=((new_smallest/smallest)>>1)-1;
    return ripple | one;
}
void Sieve( void )
{
    int i, j;
    char p[Nmax]={0};
    for( i=1; ((i*i)<<1)+(i<<1) <= N; ++i )
        if( 0 == (p[i>>3] & (1<<(i&7) ) ) )
          for( j=((i*i)<<1)+(i<<1); (j<<1)+1 <= N;  j+=(i<<1)+1 )
                p[j>>3]|=(1<<(j&7));
   dvi1.push_back(2);
   for( i=1; (i<<1)+1 <= N; ++i )
       if( 0 == (p[i>>3] & (1<<(i&7) ) ) )
           dvi1.push_back(2*i+1);
}
int main( void )
{
    Sieve();
    bool ok;
    int sign, j;
    lld m, A, B, pr, s, till, k, g, h;
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    in>>m;
    for( ; m; --m )
    {
        in>>A>>B;
        for( j=0; dvi1[j]*dvi1[j] <= B; ++j )
            if( 0 == B%dvi1[j] )
            {
                dvi1B.push_back(dvi1[j]);
                for( ; 0 == B%dvi1[j]; B/=dvi1[j] );
            }
        if( B > 1 && dvi1[j]*dvi1[j] >= B )
            dvi1B.push_back(B);
        s=0; ok=true;
        till=(1<<dvi1B.size());
        for( s=0, sign=-1, k=1; k < till && ok; ++k )
        {
            sign*=-1;
            for( g=(1<<k)-1; g < till; g=next_nbits(g) )
            {
                pr=1;
                for( h=0; (1<<h) <= g; ++h )
                    if( g & (1<<h) )
                    {
                        pr*=dvi1B[h];
                        if( pr > A )
                        {
                            ok=false;
                            break;
                        }
                    }
                s+=1LL*sign*A/pr;
            }
        }
        out<<(A-s)<<'\n';
        dvi1B.clear();
    }
    return 0;
}