/* 
 * 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 > div1, div1B;
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));
   div1.push_back(2);
   for( i=1; (i<<1)+1 <= N; ++i )
       if( 0 == (p[i>>3] & (1<<(i&7) ) ) )
           div1.push_back(2*i+1);
}
int main( void )
{
    Sieve();
    bool ok;
    int sign, j, stop=div1.size();
    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; j < stop && div1[j]*div1[j] <= B; ++j )
            if( 0 == B%div1[j] )
            {
                div1B.push_back(div1[j]);
                for( ; 0 == B%div1[j]; B/=div1[j] );
            }
        if( B > 1 && div1[j]*div1[j] >= B )
            div1B.push_back(B);
        s=0; ok=true;
        till=(1<<div1B.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*=div1B[h];
                        if( pr > A )
                        {
                            ok=false;
                            break;
                        }
                    }
                s+=1LL*sign*A/pr;
            }
        }
        out<<(A-s)<<'\n';
        div1B.clear();
    }
    return 0;
}