#include <bits/stdc++.h>

FILE *in = fopen("pinex.in", "r"), *out = fopen("pinex.out", "w") ;

std::vector<long long> getPrimeDivisors(long long B) {
        std::vector<long long> ret ;
        for (long long divisor(2) ; divisor * divisor <= B ; ++ divisor) {
                if (B % divisor == 0) {
                        ret.push_back(divisor) ;
                        for ( ; B % divisor == 0 ; B /= divisor) ;
                }
        }
        if (B > 1) {
                ret.push_back(B) ;
        }
        return ret ;
}

long long compute(long long state, long long divisors, std::vector<long long> primeDivisors, long long limit) {
        long long numberSubSets = __builtin_popcount(state) ;
        long long setCoef = ((numberSubSets % 2) ? 1 : -1) ;
        long long currentDivisor(1) ;
        for (long long i = 0 ; i < divisors ; ++ i) {
                if ((state >> i) & 1) {
                        currentDivisor *= primeDivisors[i] ;
                }
        }
        return (limit / currentDivisor) * setCoef ;
}

long long solve(long long A, long long B) {
        std::vector<long long> primeDivisors = getPrimeDivisors(B) ;
        long long divisors(primeDivisors.size()) ;
        long long ret(0) ;
        for (long long state(1) ; state < (1 << divisors) ; ++ state) {
                ret += compute(state, divisors, primeDivisors, A) ;
        }
        return ret ;
}

int main() {
        int tests ;
        long long A, B ;
        fscanf(in, "%d", &tests) ;
        for (long long i = 1 ; i <= tests ; ++ i) {
                fscanf(in, "%lld %lld", &A, &B) ;
                long long ans = A - solve(A, B) ;
                fprintf(out, "%lld\n", ans) ;
        }
}