#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#define NMax 501
#define MMax 200000
#include <time.h>
using namespace std;
struct intrebare
{
	int a, b; 
};
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;
    for (int i = 0; i < m; i++)
    {
		fscanf(f, "%d %d", &v[i].a, &v[i].b);
    }
	int div[NMax];
	for (int i = 0; i < m; i++)
	{
		int d = 2; int b = v[i].b, k = 0;
		if (!(b % d))
		{
			div[k++] = d;
			while (!(b % d))
			{
				b /= d;
			}
		}
		for (d = d + 1; d <= b ; d += 2)
		{
			if (!(b % d))
			{
				div[k++] = d;
				while (!(b % d))
				{
					b /= d;
				}
			}
		}
		result = 0;
		int nrDivNeprimi = 0;
		for (int z = 1; z < (1<<k); z++)
		{
			int val = 1, sign = 0;
			for (int j = 0; j < k; 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;
}