#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int t, i, j, p, d, tot, x;
	long long n, k, ras, prod;
	ifstream fin( "pinex.in" );
	ofstream fout( "pinex.out" );
	fin >> t;
	for( i = 0; i < t; i++ ){
		vector <long long> v;
		fin >> n >> k;
		d = 2;
		while( 1ll * d * d <= k ){
			if( k % d == 0 ){
				v.push_back( d );
				while( k % d == 0 ){
					 k /= d;
				}
			}
			d++;
		}
		if( k > 0 ){
			v.push_back( k );
		}
		ras = 0;
		for( j = 0; j < ( 1 << ( v.size() ) ); j++ ){
			//cout << j << '\n';
			x = j;
			tot = p = 0;
			prod = 1;
			while( x > 0 ){
				if( x % 2 == 1 ){
					prod *= v[p];
					tot++;
				}
				x /= 2;
				p++;
			}
			if( tot % 2 == 1 ){
				prod = -prod;
			}
			//cout << prod << ' ';
			ras += n / prod;
		}
		//cout << '\n';
		fout << ras << '\n';
		v.clear();
	}
	return 0;
}