#include <fstream>
#include <string.h>

using namespace std;
const int N = 1000005;
typedef long long ll;

char isPrime[N];    // prime sieve
ll prime[100000];   // prime factors < N;
ll pfact[16];       // prime factors of B;

int main()
{
    ifstream f ("pinex.in");
    ofstream g ("pinex.out");
    memset(isPrime, 1, sizeof(isPrime));

    prime[0] = 0;
    for (ll p = 2; p < N; p++)
    {
        if (isPrime[p])
        {
            for (ll j = 2*p; j < N; j += p)
                isPrime[j] = 0;
            prime[++prime[0]] = p;
        }

    }

    int M;
    ll A, B;
    f >> M;
    while (M--)
    {
        f >> A >> B;

        pfact[0] = 0;
        int i = 1;
        while (B > 1)
        {
            if (B % prime[i] == 0)
            {
                pfact[++pfact[0]] = prime[i];
                while (B % prime[i] == 0) B /= prime[i];
            }

            if (prime[i] * prime[i] > B && B > 1)
            {
                pfact[++pfact[0]] = B;
                B = 1;
            }
            ++i;
        }

        int t = pfact[0];
        ll neprime = 0;
        for (int n = 1; n < (1 << t); n++)
        {
            int cnt = 0;
            ll prod = 1;
            for (int j = 0; j < t; j++)
                if (n & (1 << j)) {
                    prod *= pfact[j+1];
                    cnt++;
                }
            if (cnt % 2) neprime += A / prod;
            else neprime -= A / prod;
        }
        g << A - neprime << '\n';

    }

    return 0;
}