#include<bits/stdc++.h>
#define NAX 1000010
using namespace std;
using ll = long long;

ifstream f("pinex.in");
ofstream g("pinex.out");

vector<int>prim;
bitset<NAX>viz;

void ciur()
{
    for(int i = 4 ; i <= 1e6 ; i += 2)
        viz[ i ] = 1;
    for(int i = 3 ; i * i <= 1e6 ; i += 2)
    {
        if(viz[ i ] == 0)
            for(int j = i * i ; j <= 1e6 ; j += i)
                viz[ j ] = 1;
    }
    prim.push_back( 2 );
    for(int i = 3 ; i <= 1e6 ; i += 2)
        if( viz[ i ] == 0 )
            prim.push_back( i );
}



int main()
{
    int t;
    ciur();
    f >> t;
    for( ; t ; --t)
    {
        ll a, b;
        f >> a >> b;
        vector<ll>divi;
        for(int i = 0 ; 1LL * prim[ i ] * prim[ i ] <= b ; ++i)
        {
            if( b % prim[ i ] == 0)
            {
                divi.push_back( prim[ i ] );
                while( b % prim[ i ] == 0)
                {
                    b /= prim[ i ];
                }
            }
        }
        if( b > 1 )
            divi.push_back( b );
        ll sol = a;
        for( ll i = 1 ; i < ( 1LL << divi.size() ); ++i)
        {
            ll sig = 1, prod = 1;
            for(int j = 0 ; j < divi.size() ; ++j)
                if( i & ( 1LL << j ))
            {
                sig *= -1;
                prod *= divi[ j ];
            }
            sol = sol + 1LL* a/prod * sig;
        }
        g << sol << '\n';
    }
}