#include <bits/stdc++.h>

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

typedef long long i64 ;

const int MV = 45e3 ;

std::vector<i64> SIEVE() {
        std::bitset<MV> sieve ;
        std::vector<i64> ret ;
        for (int i = 2 ; i <= MV ; ++ i) {
                if (sieve[i] == 0) {
                        ret.push_back(i) ;
                        for (int j = i * i ; j <= MV ; j += i) {
                                sieve[j] = 1 ;
                        }
                }
        }
        return ret ;
}

std::vector<i64> getPrimeDivisors(i64 B, std::vector<i64> primeNumbers) {
        std::vector<i64> ret ;
        for (int i = 0 ; i < primeNumbers.size() && primeNumbers[i] * primeNumbers[i] <= B ; ++ i) {
                if (B % primeNumbers[i] == 0) {
                        ret.push_back(primeNumbers[i]) ;
                        for ( ; B % primeNumbers[i] == 0 ; B /= primeNumbers[i]) ;
                }
        }
        if (B > 1) {
                ret.push_back(B) ;
        }
        return ret ;
}

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

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

int main() {
        int tests ;
        i64 A, B ;
        fscanf(in, "%d", &tests) ;
        std::vector<i64> primeNumbers = SIEVE() ;
        for (i64 i = 1 ; i <= tests ; ++ i) {
                fscanf(in, "%lld %lld", &A, &B) ;
                i64 ans = A - solve(A, B, primeNumbers) ;
                fprintf(out, "%lld\n", ans) ;
        }
}