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

int n;
pair<long long, long long> query[501];

void read() {
    int i;
    ifstream f("pinex.in");
    f >> n;
    for (i = 1; i <= n; i++)
        f >> query[i].first >> query[i].second;
    f.close();
}

bitset<1000001> e;
vector<int> primes;

void Ciur() {
    int i, j;
    for (i = 2; i * i <= 1000000; i++)
        if (!e[i])
            for (j = 2; j * i <= 1000000; j++)
                e[i * j] = 1;
    for (i = 2; i <= 1000000; i++)
        if (!e[i])
            primes.push_back(i);
}

int divi[105];

void solve() {
    int i, d, l, j, k, nr;
    long long a, b, prod, sum;
    Ciur();
    ofstream g("pinex.out");
    for (i = 1; i <= n; i++) {
        a = query[i].first, b = query[i].second;
        l = 0;
        for (d = 0; primes[d] * primes[d] <= b; d++) {
            if (b % primes[d] != 0)
                continue;
            divi[++l] = primes[d];
            while (b % primes[d] == 0) 
                b /= primes[d];
        }
        if (b > 1)
            divi[++l] = b;
        sum = 0;
        for (j = 1; j < (1 << l); j++) {
            prod = 1, nr = 0;
            for (k = 1; k <= l; k++)
                if (j & (1 << (k - 1))) {
                    prod *= divi[k];
                    nr++;
                }
            if (nr & 1)
                sum += a / prod;
            else sum -= a / prod;
        }
        g << a - sum << '\n';
    }
    g.close();
}

int main() {
    read();
    solve();
    return 0;
}