#include <fstream>
#include <queue>
#include <assert.h>
#define int long long

using namespace std;
bool ciur[1000007];
int sum=0, a;
vector <int> primes, factori;

int bkt(int poz, int put, int sign)
{
	if(poz==factori.size())
	{
		sum+=sign*(a/put);
		return 0;
	}

	bkt(poz+1, put, sign);
	bkt(poz+1, put*factori[poz], sign*(-1));
}

int32_t main()
{

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

		ciur[0]=ciur[1]=1;
		for(int k=2;k<1000007;k++)
		{
			if(ciur[k]==0)
			{
				primes.push_back(k);
				for(int j=k*k;j<1000007;j+=k)
					ciur[j]=1;
			}
		}

    int t, b;
    cin>>t;

    for(int h=0;h<t;h++)
		{
			cin>>a>>b;

			for(auto d : primes)
			{
				if(d*d>b)
					break;
				if(b%d==0)
				{
          factori.push_back(d);
          while(b%d==0)
						b/=d;
				}
			}

			if(b>1)
			{
				factori.push_back(b);
        b=1;
			}

			assert(factori.size() <= 12);

			sum=0;
			bkt(0, 1, 1);

			cout<<sum<<'\n';
			factori.clear();
		}

    return 0;
}