#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 < ll > Prim, 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;
}