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

fstream fin ("pinex.in", ios::in);
fstream fout ("pinex.out", ios::out);

typedef long long int64;

//<ciur>
#define MAXP 1000010
#define NUMP 80000
bitset <MAXP> p;
int64 prim[NUMP], np = 0;

void ciur ()
{
	for (int i = 1; ((i * i) << 1) + (i << 1) < MAXP; ++i) {
		if (!p[i]) {
			for (int j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= MAXP; j += (i << 1) + 1) {
				p[j] = true;
			}
		}	
	}
	
	prim[0] = 2; np++;
	for (int i = 1; (i << 1) < MAXP; ++i) {
		if (!p[i]) {
			prim[np++] = (i << 1) + 1;
		}
	}
}
//</ciur>

void do_test ()
{
	int64 a, b;
	fin >> a >> b;
		
	vector<int64> fp;
	
	int d = 0;
	while (b > 1) {
		if (b % prim[d] == 0) {
			fp.push_back (prim[d]);
			
			while (b % prim[d] == 0) {
				b /= prim[d];	
			}	
		}	
		if (prim[d] * prim[d] > b && b > 1) {
			fp.push_back (b);
			break;
		}
		
		++d;
	}	
	
	int n = fp.size ();
	int64 sol = a;
		
	for (int i = 1; i < (1 << n); ++i) {
		int64 nr = 1, nf = 0;
		
		for (int k = 0; k < n; ++k) {
			if (i & (1 << k)) {
				nr *= fp[k];
				++nf;	
			}
		}	
		
		if (nf % 2) {
			sol = sol - (int64)a / nr;	
		} else {
			sol = sol + (int64)a / nr;
		}
	}
				
	fout << sol << endl;
}

int main ()
{
	ciur ();
	
	int m;
	fin >> m;
	
	while (m--) {
		do_test ();
	}
	
	fin.close ();
	fout.close ();
	return 0;
}