#include <fstream>
#include <cstring>
#include <vector>
#include <bitset>
using namespace std;

#define MAX_VAL 1000000

int main() {
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	
	vector<int> p;

	{
		bitset<MAX_VAL + 1> isPrime;
		for(int i=2;i*i<=MAX_VAL;++i) {
			for(int j=i*i;j<=MAX_VAL;j+=i)
				isPrime[j] = true;
		}
		for(int i=2;i<=MAX_VAL;++i)
			if(!isPrime[i])
				p.push_back(i);
	}

	int T;
	f>>T;
	while(T--) {
		long long A,B;
		f>>A>>B;

		vector<long long> fact;
		
		{
			for(int i=0;i<p.size() && p[i] * p[i] <= B; ++i) {
				if(B % p[i] == 0)
					fact.push_back(p[i]);
				while(B % p[i] == 0)
					B /= p[i];
			}
			if(B > 1)
				fact.push_back(B), B = 1;
		}
		long long div = 0; //# of elements that have at least a factor in common with B

		for(int i=1;i < 1<<fact.size(); ++i) {

			long long prod = -1;
			for(int j=0;j<fact.size();++j) {
				if( (1<<j&i) == 1<<j ) {
					prod = -prod * fact[j];
				}
			}
			div += A / prod;
		}

		g << A - div << endl;
	}

}