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

bitset<1000000> isprime;
vector<int> prime;
vector<int>::iterator it;
long long a, b, ans;
vector<int> p;

void dfs(int i, long long d)
{
	if (i >= p.size())
		ans += a/d;
	else {
		dfs(i+1,d);
		dfs(i+1,d*p[i]);
	}
}
		
int main()
{
	for (int i = 3; i < 1e6; i += 2)
		isprime[i] = true;
	for (int i = 3; i < 1e3; i += 2) {
		if (isprime[i])
			for (int j = i*i; j < 1e6; j += 2*i)
				isprime[j] = false;
	}
	prime.push_back(2);
	for (int i = 3; i < 1e6; i += 2)
		if (isprime[i])
			prime.push_back(i);
	prime.push_back(1000003);

	ifstream fin("pinex.in");
	ofstream fout("pinex.out");
	int m;
	fin >> m;
	for (; m > 0; --m) {
		fin >> a >> b;
		int sqrtb = sqrt(b);
		for (it = prime.begin(); *it <= sqrt(b); ++it) {
			if (b % *it == 0) {
				p.push_back(-*it);
				do {
					b /= *it;
				} while (b % *it == 0);
				sqrtb = sqrt(b);
			}
		}
		if (b != 1) p.push_back(-b);
		ans = 0;
		dfs(0,1);
		fout << ans << '\n';
		p.clear();
	}
	return 0;
}