/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on March 25, 2010, 3:17 PM
 */
#include <vector>
#include <cstdlib>
#include <fstream>
#define NMax 1000003

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