#include <iostream>
#include <fstream>

ifstream fin("pinex.in");
ofstream fout("pinex.out");

using namespace std;
long long d[12]; //  d[1].....d[n]
int n;
long long a, b, ans;
int s[12];

bool ciur[1000001];
int p[200000]; // p[1]=2  p[2]=3 .......p[cnt]<=1 000 000
int cnt;
void calculare() {
    ciur[0] = 1;
    ciur[1] = 1;
    for (int i = 2; i * i <= 1000001; i++)
        if (!ciur[i]) {
            for (int j = i; i * j <= 1000001; j++)
                ciur[i * j] = 1;
        }
    for (int i = 2; i <= 1000001; i++)
        if (!ciur[i])
            p[++cnt] = i;
}

void produs(int k) {
    long long p = 1;

    for (int i = 1; i <= k; i++) {
        p *= d[s[i]];
    }

    if (k % 2 == 0) ans = ans - a / p;
    else
        ans += (a / p);
}



void bkt(int k, int nr) {
    for (int i = s[k - 1] + 1; i <= n + k - nr; i++) {
        s[k] = i;

        if (k == nr) {
            produs(k);
        }
        else
            bkt(k + 1, nr);

    }
}

int main()
{
    int m; fin >> m;
    calculare();
    for (int i = 1; i <= m; i++)
    {
        fin >> a >> b;
        ans = 0;
        n = 0;
        for (int j = 1; j <= cnt && p[j] * p[j] <= b; j++)
            if (b % p[j] == 0)
            {
                d[++n] = p[j];

                while (b % p[j] == 0)
                    b /= p[j];
            }
        if (b > 1) { n++;  d[n] = b; }

        for (int j = 1; j <= n; j++)
            bkt(1, j);

        fout << a - ans << '\n';
    }

    return 0;
}