#include <fstream>
#include <cmath>
#include <vector>
using namespace std;

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

vector <int> diviz;
vector <int> prime;
int f[1000004], k;
long long raspuns, produs;


void pinex( long long a )
{
    int marime = prime.size();
    for ( int i = 1; i < (1<<marime); ++i )
    {
        k = 0;
        produs = 1;
        for ( int j = 0; j < marime; ++j )
        {
            if ( (1<<j)& i )
            {
                k++;
                produs *= prime[j];
            }
        }
        if ( k % 2 == 0 )
            raspuns -= a/produs;
        else
            raspuns += a/produs;
    }
}

void ciur()
{
    for ( int i = 2; i <= 1000000; ++i )
    {
        if ( f[i] == 0 )
        {
            diviz.push_back(i);
            for ( int j = i; j <= 1000000; j += i )
                f[j] = 1;
        }
    }
}

int main()
{
    int m;
    long long a, b;
    fin>>m;
    ciur();
    while ( m-- )
    {
        raspuns = 0;
        prime.clear();
        fin>>a>>b;
        for ( auto x:diviz )
        {
            if ( b % x == 0)
            {
                prime.push_back(x);
                while ( b % x == 0 )
                    b /= x;
            }
        }
        if (b > 1)
            prime.push_back(b);
        pinex(a);
        fout<<a - raspuns<<'\n';

    }
}