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

using namespace std;

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


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

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)
                v[j] = 1;
}

void rez()
{
    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(t = 1 << k , i = 1; i < t; i++)
        {
            for(r = 1, s = j = 0; j<k; j++)
                if( (i & (1 << j))>0)
                    s++, r *= a[j+1];
            l += ((s%2 == 0 ? 1 : -1) * x / r);
        }

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

int main()
{
    ciur();
    rez();

    return 0;
}