#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#define ff(i,n) for (i = 1; i <= n; ++i)
#define dd(i) out << i <<'\n'
# define z6 1000000
using namespace std;
bitset <z6 + 5> c;
int p[80070], up, d[80070], ud;
long long A;
 
void eratostene() {
     
    long long i, j;
    for (i = 4; i <= z6; i+=2) {
        c[i] = 1;
    }
    for (i = 3; i <= z6; ++i) {
        if (!c[i]) {
            for (j = 1ll * i * i; j <= z6; j += (i + i)) {
                c[j] = 1;
            }
        }
    }
}
void desc(long long  B) {
    int i;
    ud = 0;
    for (i = 1; i <= up && p[i] <= sqrt(B); ++i) {
        if (!(B % p[i])) {
            d[++ud] = p[i];
			while (!(B % p[i])) {
				B /= p[i];
        	}
        }
    }
	if(B > 1) d[++ud] = B;
}
 
long long rezolva(long long  B) {
    long long m = (1 << ud) - 1, i, j;
    long long D = 1, nrb;
    long long R = 0;
    ff(i, m) {
        nrb = 0;
        D = 1;
        for (j = 0; (1ll << j) <= i; ++j) {
            if (i & (1ll << j)) {
                ++nrb;
                D *= d[j + 1];
            }
        }
         
        if(nrb & 1) {
            R += (A / D);
        } else {
            R -= (A / D);
        }
    }
    return R;
}
 
int main(){
    /*freopen ("geamuri.in", "r", stdin);
    freopen ("geamuri.out", "w", stdout);*/
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    int i;
    eratostene();
    for (i = 2; i <= z6; ++i) {
        if (!c[i]) {
            p[++up] = i;
        }
    }
    long long B;
    int M;
    in >> M;
    while (M--) {
        in >> A >> B;
        desc(B);
        dd(A - rezolva(B));
    }
}