#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#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'
using namespace std;
bitset <60005> c;
int p[6070], up, d[6070], ud;
long long A;

void eratostene() {
	
	long long i, j;
	for (i = 4; i <= 60000; i+=2) {
		c[i] = 1;
	}
	for (i = 3; i <= 60000; ++i) {
		if (!c[i]) {
			for (j = 1ll * i * i; j <= 60000; j += (i + i)) {
				c[j] = 1;
			}
		}
	}
}
void desc(int B) {
	int i;
	ud = 0;
	for (i = 1; i <= up && p[i] <= B; ++i) {
		if (!(B % p[i])) {
			d[++ud] = p[i];
		}
	}
}

int rezolva(int 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 <= 60000; ++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));
	}
}