#include<bits/stdc++.h>
using namespace std;

const int BMAX = 1e6;
long long a, b, ans;
vector<int> primes, div_nr;
bool ciur[BMAX + 5];

void create_Ciur()
{
    for(int i = 2; i <= BMAX; i++)
    {
        if(!ciur[i])
        {
            primes.push_back(i);
            for(int j = i * 2; j <= BMAX; j += i)
            {
                ciur[j] = true;
            }
        }
    }
}

void bkt(int pos, int sign, long long prod)
{
    if(pos == div_nr.size())
    {
        ans += sign * (a / prod);
        return;
    }

    bkt(pos + 1, sign, prod);
    bkt(pos + 1, sign * -1, prod * div_nr[pos]);
}

void query()
{
    ans = 0;
    div_nr.clear();
    cin >> a >> b;

    for(auto nr : primes)
    {
        if(1LL * nr * nr > b)
            break;

        if(b % nr == 0)
        {
            div_nr.push_back(nr);
            while(b % nr == 0)
                b /= nr;
        }
    }

    if(b > 1)
    {
        div_nr.push_back(b);
        b = 1;
    }

    bkt(0, 1, 1);

    cout << ans << "\n";
}

int main()
{
    create_Ciur();
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    int t;
    cin >> t;

    while(t--)
        query();
}