#include <vector>
#include <fstream>
#define N 1000001

using namespace std;

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

long long p[N],a[101],i,j,o,x,y,s,r,d,k,t,m,l;
bool v[N];

void ciur()
{


    for( m = N - 1, i = 2, cin >> o; i <= m ; i++)
        if(!v[i])
            for(p[++d] = i, j = i * i; j <= m ; j += i) // il bagam in vectorul de numere prime p
                v[j] = 1; // e multiplu de divizor prim
}

void rez()
{
    int i, j;

    while(o--)
    {
        for(cin >> x >> y, l = x, k = 0, i = 1;
            i * i <= y ; i++)
            if(!(y % p[i]))
                for(a[++k] = p[i]; !(y % p[i]) ; y /= p[i]);

        if(y > 1)
            a[++k] = y;

        for(int t = 1 << k , i = 1 ; i < t ; i++)
        {
            for(r = 1, s = j = 0 ; j < k ; j++)
                if(  (i & (1 << j)) )
                     s++, r *= a[j + 1];

            l += (( (s & 1) == 0) ? 1 : -1 ) * x / r;
        }

        cout << l << '\n';
    }


}

int main()
{
    ciur();
    rez();
    return 0;
}