#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
vector <int> prime, divp;
bool c[1000005];
void build_ciur()
{
    int i, j;
    c[0] = c[1] = 1;
    for(i = 4; i <= 1e6; i += 2)
        c[i] = 1;
    for(i = 3; i * i <= 1e6; i += 2)
        if(c[i] == 0)
            for(j = i * i; j <= 1e6; j += i)
                c[j] = 1;
    for(i = 2; i <= 1e6; i ++)
        if(c[i] == 0)
            prime.push_back(i);
}
void desc(int a)
{
    divp.clear();
    int i = 0;
    while(i < prime.size() &&  prime[i] * prime[i] <= a)
    {
        if(a % prime[i] == 0)
        {
            divp.push_back(prime[i]);
            while(a % prime[i] == 0)
                a /= prime[i];
        }
        i ++;
    }
    if(a > 0)
        divp.push_back(a);
}
int32_t main()
{

    int q, a, b, i, j, n, ans = 0, nr = 1, cntb = 0;
    cin >> q;
    build_ciur();
    while(q --)
    {
        cin >> a >> b;
        desc(b);
        n = divp.size();
        ans = 0;
        for (i = 0; i < (1 << n); i ++)
        {
            cntb = 0;
            nr = 1;
            for (j = 0; j < n; j ++)
                if (i & (1 << j))
                {
                    cntb ++;
                    nr *= divp[j];
                }
            if (cntb % 2 == 0)
                ans += a / nr;
            else
                ans -= a / nr;
        }
        cout << ans << '\n';
    }
    return 0;
}