include <bits/stdc++.h>

using LL = long long;

const int PRIME_MAX = (int)10e6;

LL a, b;

std::vector<int> primes;

std::vector<LL> factors;

std::bitset<PRIME_MAX> not_prime;

void sieve() {

not_prime[1] = 1;

primes.push_back(2);

for (int i = 4; i < PRIME_MAX; i += 2)

not_prime[i] = 1;

for (int i = 3; i < PRIME_MAX; i += 2) {

if (not_prime[i])

continue;

primes.push_back(i);

for (int j = 2 * i; j < PRIME_MAX; j += i)

not_prime[j] = 1;

}

}

void find_factors() {

factors.clear();

std::vector<int>::iterator prime = primes.begin();

for (auto p: primes) {

if (p * p > b)

break;

if (b % p == 0) {

factors.push_back(p);

while (b % p == 0)

b /= p;

}

}

if (b > 1) {

factors.push_back(b);

}

}

void pinex() {

LL result = a;

for (int subset = 1; subset < (1 << factors.size()); subset++) {

LL product = 1;

int sign = 1;

for (int j = 0; j < factors.size(); j++) {

if (subset & (1 << j)) {

product *= factors[j];

sign = -sign;

}

}

result += sign * a / product;

}

printf("%lld\n", result);

}

int main() {

freopen("pinex.in", "r", stdin);

freopen("pinex.out", "w", stdout);

sieve();

int t;

scanf("%d", &t);

while (t--) {

scanf("%lld %lld", &a, &b);

find_factors();

pinex();

}

}