#include <iostream>
#include <fstream>

using namespace std;

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

int v[10001];
int nrdiv;

void divizori_primi(long long b)
{
    nrdiv = 0;
    long long i;
    if( b % 2 == 0 )
    {
        nrdiv++;
        v[nrdiv] = 2;
    }
    for( i = 3; i <= b; i+=2 )
    {
        if( b % i == 0 )
        {
            nrdiv++;
            v[nrdiv] = i;
            while ( b % i == 0)
                b /= i;
        }
    }
}

int main()
{
    int m, i, j, q;
    long long a, b;
    f >> m;
    for( i = 1; i <= m; i++ )
    {
        f >> a >> b;
        divizori_primi(b);
        long long sum=0;
        int k = (1 << nrdiv);
        for( j = 1; j < k; j++ )
        {
            int par = 0;
            for ( q = 0; q < nrdiv; q++ )
                par += (j >> q) % 2;
            long long x = 1;
            for ( q = 0; q < nrdiv; q++ )
                if ((j >> q ) % 2 == 1)
                    x *= v[q+1];
            if( par %2 == 1 )
                sum += a/x;
            else sum -= a/x;
        }
        g << a - sum << '\n';
    }
    return 0;
}