#include <fstream>
#include <vector>

#include <cmath>
#include <cstring>
using namespace std;

const int MAX_VAL = 1000002;
const int MAX_F = 22;

int M;
vector < int > primes;
long long A, B;
long long a[MAX_F];
bool isPrime[MAX_VAL + 2];

int main() {
    ifstream f("pinex.in");
    ofstream g("pinex.out");

    memset(isPrime, 1, sizeof(isPrime));

    isPrime[0] = isPrime[1] = 0;
    primes.push_back(2);
    for(int i = 4; i <= MAX_VAL; i += 2)
        isPrime[i] = 0;
    for(int i = 3; i <= MAX_VAL; i += 2)
        if(isPrime[i]) {
            primes.push_back(i);
            for(int j = i + i; j <= MAX_VAL; j += i)
                isPrime[j] = 0;
        }

    f >> M;
    for(int q = 1; q <= M; ++q) {
        f >> A >> B;

        int n = 0;
        for(int i = 0; i < (int) primes.size() && primes[i] < B; ++i)
            if(B % primes[i] == 0) {
                a[++n] = primes[i];
                while(B % primes[i] == 0)
                    B /= primes[i];
            }

        if(B > 1)
            a[++n] = B;

        long long temp = 0;
        for(int conf = 1; conf < (1 << n); ++conf) {
            int k = 0;
            long long p = 1;

            for(int i = 0; i < n; ++i)
                if(conf & (1 << i)) {
                    ++k;
                    p *= a[i + 1];
                }

            if(k % 2)
                temp += A / p;
            else temp -= A / p;
        }

        long long ans = A - temp;

        g << ans << "\n";\
    }

    f.close();
    g.close();

    return 0;
}