/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on March 25, 2010, 3:17 PM
 */
#include <vector>
#include <fstream>
#include <cstdlib>
#define NM 1000003
#define Nmax N/16+1

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