#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <cctype>
#define BUFF_SIZE 300001
#define LIM 1000000

using namespace std;

bitset<LIM> mark;
vector<int> primes;
vector<int> fact;

ifstream in("pinex.in");
ofstream out("pinex.out");

char buffer[BUFF_SIZE];
int pos = 0;

void Read(long long int& a) {

    while (!isdigit(buffer[pos]))
        if (++pos == BUFF_SIZE)
            in.read(buffer, BUFF_SIZE), pos = 0;
    a = 0;
    while (isdigit(buffer[pos]))
    {
        a = a * 10 + buffer[pos] - '0';
        if (++pos == BUFF_SIZE)
            in.read(buffer, BUFF_SIZE), pos = 0;
    }
}

void ciur() {

    for (int i = 3; i * i <= LIM; i += 2) {

        if (!mark.test(i)) {

            for (int j = i * i; j <= LIM; j += 2 * i)
                mark.set(j);
        }
    }

    primes.push_back(2);
    for (int i = 3; i <= LIM; i += 2)
        if (!mark.test(i))
            primes.push_back(i);
}

void desc(long long int n) {

    int pos = 0;
    fact.clear();

    while (primes[pos] * primes[pos] <= n) {

        if (n % primes[pos] == 0) {

            while (n % primes[pos] == 0)
                n /= primes[pos];
            fact.push_back(primes[pos]);
        }

        if (++pos == (signed) primes.size())
            break;
    }

    if (n != 1)
        fact.push_back(n);
}

int main() {

    ciur();
    int nr_bits;
    long long M;
    long long int A, B;
    long long int div = 1;
    long long int sum = 0;

    for (Read(M); M; --M) {

        Read(A), Read(B);
        desc(B);

        sum = 0;
        for (int i = 1; i < (1 << fact.size()); i++)
        {
            nr_bits = 0;
            div = 1LL;
            for (int j = 0; (1 << j) <= i; j++)
                if (i & (1 << j))
                {
                    nr_bits++;
                    div *= fact[j];
                }
            if (nr_bits & 1)
                sum += (A / div);
            else
                sum -= (A / div);
        }

        out << A - sum << "\n";
    }

    in.close();
    out.close();
    return 0;
}