#include <fstream>
#include <vector>
#include <bitset>
#include <iostream>
using namespace std;

int prime[78499], n, K;
long long d[12],x,a;
void ciurul()
{
    const int VMAX = 1e6;
    bitset <1+VMAX> c;
    int i = 1;
    prime[K++] = 2;
    prime[K++] = 3;
    for (i = 5; i * i < VMAX; i+=6)
    {
        if (!c[i])
        {
            prime[K++] = i;
            for (int mult = i * i; mult <= VMAX; mult += i)
            {
                c[mult] = 1;
            }
        }
        int x = i + 2;
        if (!c[x])
        {
            prime[K++] = x;
            for (int mult = x * x; mult <= VMAX; mult += x)
            {
                c[mult] = 1;
            }
        }
    }
    for (; i<=VMAX; i+=6)
    {
        if (!c[i])
        {
            prime[K++] = i;
        }
        if (!c[i+2])
        {
            prime[K++] = i+2;
        }
    }
    prime[K] = VMAX;
}

inline long long prime_cu_b()
{
    n = 0;
    for (int i = 0; (long long)prime[i] * prime[i] <= x; i++)
    {
        if (x % prime[i] == 0)
        {
            d[n++] = prime[i];
            do
            {
                x /= prime[i];
            }while (x % prime[i] == 0);
        }
    }
    if (x != 1)
        d[n++] = x;
    long long rez = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        long long p = 1;
        int nb = 0;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))///d[j] apartine submultimii codif. de i
            {
                p *= d[j];
                nb++;
            }
        }
        if (!(nb&1))
        {
            rez += a / p;
        }
        else
        {
            rez -= a / p;
        }
    }
    return rez;
}

int main()
{
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    ciurul();
    int n;
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> a >> x;
        out << prime_cu_b() << '\n';
    }
    in.close();
    out.close();
    return 0;
}