#include <fstream>
#include <cmath>
#include <vector>

#define ll long long

using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

int t;
const int VALMAX = 1e6;
char c[VALMAX + 1];
vector<ll> prime;

void Eratostene()
{
    c[0] = c[1] = 1;
    for(int i = 2; i * i <= VALMAX; i++)
        if(!c[i])
            for(int j = 2; i * j <= VALMAX; j++)
                c[i * j] = 1;

    for(int i = 2; i <= VALMAX; i++)
        if(!c[i])
            prime.push_back(i);
}

void GetFact(ll n, vector<int> &fact)
{
    int ind = 0;
    ll d = prime[ind];

    while(n > 1)
    {
        if(n % d == 0)
        {
            fact.push_back(d);
            while(n % d == 0)
                n /= d;
        }

        d = prime[++ind];
        if(d * d > n)
            d = n;
    }
}

ll PINEX(ll A, vector<int> &fact)
{
    int n = fact.size();
    ll ans = 0;

    for(int i = 1; i <= (1 << n) - 1; i++)
    {
        ll prod = 1;
        int nr_elem = 0;

        for(int j = 0; j < n; j++)
            if((1 << j) & i)
            {
                nr_elem++;
                prod *= 1LL * fact[j];
            }
        
        // cout << prod << ' ';
        if(nr_elem % 2 == 0)
            ans -= A / prod;
        else
            ans += A / prod;

    }

    return ans;
}

void test_case()
{
    ll A, B;
    cin >> A >> B;

    vector<int> fact;
    GetFact(B, fact);

    ll scoate = PINEX(A, fact);
    cout << A - scoate << '\n';
}

int main()
{
    cin >> t;
    Eratostene();
    while(t--)
        test_case();

    return 0;
}