#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1000005

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");


bitset < MAX > nonprim;
vector < int > Prim;
vector < ll > v;
ll a, R, r;
int n;

void ciur()
{
    int i, j;

    nonprim[0] = nonprim[1] = 1;
    for(i = 4; i < MAX; i += 2 ) nonprim[i] = 1;
    for(i = 3; i * i < MAX; i += 2) if(nonprim[i] == 0)
        for(j = i * i; j < MAX; j += i + i) nonprim[j] = 1;

    Prim.pb(2);
    for(i = 3; i <= MAX; i += 2) if(nonprim[i] == 0) Prim.pb(i);
}

void bkt(int nr, int k, int last)
{
    int i;

    if(k == nr + 1)
    {
        if(nr % 2 == 1) R += a / r;
        else R -= a / r;
    }
    else
    {
        for(i = last + 1; i < n; i++)
        {
            r *= v[i];
            bkt(nr, k + 1, i);
            r /= v[i];
        }
    }
}

int main()
{
    ll b;
    int TT, i;

    ciur();

    fin >> TT;
    while(TT--)
    {
        v.clear();
        fin >> a >> b;

        i = 0;
        while(Prim[i] * Prim[i] <= b)
        {
            if(b % Prim[i] == 0)
            {
                v.pb(Prim[i]);
                while(b % Prim[i] == 0) b /= Prim[i];
            }
            i++;
        }

        if(b != 1) v.pb(b);

        R = 0, n = v.size();
        for(i = 1; i <= n; i++)
        {
            r = 1;
            bkt(i, 1, -1);
        }

        fout << a - R << '\n';
    }


    return 0;
}