#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>

#define MAX_PRIME_INDEX 1000001

using namespace std;

long long m,a,b, index;

int primeSieve[MAX_PRIME_INDEX];
vector<long long> primes;
vector<long long> primeDivisors;
long long result;

void sieveOfEratosthenes(){
    for (int i=2; i<MAX_PRIME_INDEX; i++){
        if (primeSieve[i] == 0){
            primes.push_back(i);

            int j=2*i;
            while (j < MAX_PRIME_INDEX){
                primeSieve[j] = 1;
                j = j+i;
            }
        }
    }
}

void collectPrimeDivisors(long long b){
    int i=0;
    primeDivisors.clear();

    while (primes[i] <= sqrt(b)){
        if ((b % primes[i]) == 0){
            int currentPrime = primes[i];
            primeDivisors.push_back(primes[i]);

            while (b % primes[i] == 0){
                b = b/primes[i];
            }
        }

        i++;
    }

    //check if the remaining is prime. It can be either a prime or 1.
    if (b > 1){
        primeDivisors.push_back(b);
    }

}

void calculate(int lastIndex, int index, long long currentProduct){

    for (int i=lastIndex+1; i<primeDivisors.size(); i++){
        long long currentDivisor =primeDivisors[i];
        long long nrOfNumbersDivisibleByPrime = a/(currentDivisor * currentProduct);

        if (nrOfNumbersDivisibleByPrime == 0){
            break;
        }

        if (index % 2 == 0){
            result = result - nrOfNumbersDivisibleByPrime;
        } else {
            result = result + nrOfNumbersDivisibleByPrime;
        }

        calculate(i, index+1, currentProduct*currentDivisor);
    }
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    sieveOfEratosthenes();

    scanf("%lld", &m);

    for (int i=0; i<m; i++){
        scanf("%lld %lld", &a, &b);

        collectPrimeDivisors(b);
        result = 0;
        calculate(-1, 1, 1);

        printf("%lld\n", (long long)a-result);
    }

    return 0;
}