#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
using LL = long long;
const LL MAX_SIZE = 1E6;
LL res;
bitset<MAX_SIZE + 1> prime;
vector<LL> prime_arr = {2};
void precalc_prime_arr()
{
prime[0] = prime[1] = 1;
for (int i = 2; i * i <= MAX_SIZE; i += 1 + i != 2)
{
if (prime[i] == 0)
{
for (int j = i; j <= MAX_SIZE / i; ++j)
{
prime[j * i] = 1;
}
}
}
for (int i = 3; i <= MAX_SIZE; i += 2)
{
if (!prime[i])
{
prime_arr.emplace_back(i);
}
}
}
void solve(LL A, LL B)
{
vector<int> prime_facs;
prime_facs.reserve(20);
int index = 0;
for (; prime_arr[index] * prime_arr[index] <= B; ++index)
{
if (B % prime_arr[index] == 0)
{
prime_facs.emplace_back(prime_arr[index]);
while (B % prime_arr[index] == 0)
{
B /= prime_arr[index];
}
}
}
if (B > 1)
{
prime_facs.emplace_back(B);
}
for (int i = 1; i < (1 << prime_facs.size()); ++i)
{
LL nr_subsets = 0, cur_product = 1;
for (LL j = 0; j < prime_facs.size(); ++j)
{
if ((1 << j) & i)
{
cur_product *= prime_facs[j];
++nr_subsets;
}
}
int sign;
if (nr_subsets % 2 == 0)
{
sign = -1;
}
else
{
sign = 1;
}
res += sign * A / cur_product;
cur_product = 1;
nr_subsets = 0;
}
}
int main()
{
precalc_prime_arr();
ifstream fin("pinex.in");
LL M;
fin >> M;
ofstream fout("pinex.out");
while (M--)
{
LL A, B;
fin >> A >> B;
solve(A, B);
fout << A - res << "\n";
res = 0;
}
}