#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
vector<int> divs;
bool ciur[1000005];
void precalc()
{
    ciur[0] = 1;
    ciur[1] = 1;

    for ( int i = 2; i <= 1e6 ; i ++ )
    {
        if (!ciur[i])
            for ( int j = i + i ; j <= 1e6 ; j += i )
            ciur[j] = 1;

        if (!ciur[i])
            divs.push_back(i);
    }
}

void solve()
{
    long long a , b ;
    cin >> a >>b ;

    vector<int> fact;
    for ( int i  = 0 ; i < divs.size() ; i ++ )
    {
        if ( divs[i] > b )
            break;

            if ( b % divs[i] == 0 )
                fact.push_back(divs[i]);
    }

    long long sz = fact.size() ;

    //cout << sz << '\n';
    long long ans = 0 ;
    for ( int i = 1; i < ( 1 << sz ) ; i ++ )
    {
        int cnt = 0 ;
        long long nr = 1 ;
        for ( int j = 0 ; j < sz ; j ++  )
        {
            if ( ( 1 << j) & i   )
            {
                cnt ++;
                nr *= fact[j];
            }
        }

        if ( cnt % 2 == 0 )
        ans -= a / nr ;
        else
            ans += a / nr ;
    }

    cout << a - ans << '\n';
}
int main()
{
    precalc();

    int test;
    cin >> test;
    while ( test -- )
    solve();
    return 0;
}