#include <fstream>
//#include <iostream>
using namespace std;
const int NMAX = 1e6 + 10;
#define int long long int
int A, B, t, primes[NMAX], p;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int desc(int num)
{
    p = 0;
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            primes[++p] = i;
            while (num % i == 0)
            {
                num /= i;
            }
            //cout << i << '\n';
        }
    }
    if (num > 1)
    {
        //cout << num << '\n';
        primes[++p] = num;
    }
    return p;
}
int solve(int a, int b)
{
    int fcnt = desc(b);
    int ans = 0;
    for (int i = 1; i <= (1 << fcnt); i++)
    {
        int cnt = 0, prod = 1;
        //cout << fcnt << '\n';
        for (int j = 0; j < fcnt; j++)
        {
            if (i & (1 << j))
            {
                prod *= primes[j + 1];
                //cout << primes[j + 1] << '\n';
                cnt ++;
            }
        }
        if (cnt % 2 == 0) 
        {
            //cout << "+" << a << ' ' << prod << '\n';
            ans += a/prod;
        }
        else
        {
            //cout << "-" << a << ' ' << prod << '\n';
            ans -= a/prod;
        }
    }
    return ans;
}
main()
{
    cin >> t;
    while (t--)
    {
        cin >> A >> B;
        cout << solve(A, B) << '\n';

    }
}