#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#define NMax 10000
#define MMax 80000
#define Max 1000000
#include <time.h>
using namespace std;
struct intrebare
{
	int a, b; 
};
int eratostene[MMax]; int  k;
void ciur()
{
	bool ciur[Max]; 
	for (int i = 2; i < Max; i++)
		ciur[i] = true;
    for ( int i = 2; i * i < Max; i++ )
    {
		if ( ciur[i] == true )
            for ( int j = i * i; j < Max; j += i )
            {
				ciur[j] = false;
			}
	}
    for ( int i = 2; i < Max; i++ )
        if ( ciur[i]  == true )
            eratostene[k++] = i;
}
int main()
{
	int m; intrebare *v;
    FILE *f = fopen("pinex.in", "r");
    FILE *g = fopen("pinex.out", "w");
    fscanf(f, "%d", &m);
	v = new intrebare[m+1];
	int result = 0, max = 0;
    for (int i = 0; i < m; i++)
    {
		fscanf(f, "%d %d", &v[i].a, &v[i].b);
		if ( v[i].b > max )
			max = v[i].b;
    }
	ciur();
	int div[NMax];
	for (int i = 0; i < m; i++)
	{
		int b = v[i].b; int indice = 0;
		for (int l = 0; l < k && b != 1; l++)
		{
			if (!(b % eratostene[l]))
			{
				div[indice++] = eratostene[l];
				while (!(b % eratostene[l]))
				{
					b /= eratostene[l];
				}
			}
		}
		if (b > 1)
			div[indice++] = b;
		result = 0;
		for (int z = 1; z < (1<<indice); z++)
		{
			int val = 1, sign = 0;
			for (int j = 0; j < indice; j++)
			{
				if ( z & (1<<j) )
				{
					val *= div[j]; 
					sign++;
				}
			}
			if (sign & 1)
				sign = 1;
			else
				sign = -1;
			result += sign * v[i].a / val;
		}
		fprintf(g, "%d\n", v[i].a - result);
	}
	
    fclose(f); fclose(g);

	return 0;
}