#include <bits/stdc++.h>

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

std::vector<int> getPrimeDivisors(int B) {
        std::vector<int> ret ;
        for (int 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 ;
}

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

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

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