#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#define NMax 501
#define Prim 31
#define MMax 80001
#include <time.h>
using namespace std;
struct intrebare
{
	int a, b; 
};

void ciur(int n, int eratostene[], int &k)
{
	bool* ciur = new bool[n+1];  k = 0;
    for (int i = 1; i <= n; i++)
		ciur[i] = true;
	 for (int i = 2; i <= n; i++)
        if (ciur[i])
        {
            eratostene[k++] = i;
            for(int j = i+i; j <= n; j += i)
                ciur[j] = false;
        }
}
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;
    }
	int *eratostene = new int[MMax], ind;
	ciur(max, eratostene, ind);
	int div[Prim];
	for (int i = 0; i < m; i++)
	{
		int b = v[i].b, k = 0;
		for (int l = 0; l < ind && b != 1; l++)
		{
			if (!(b % eratostene[l]))
			{
				div[k++] = eratostene[l];
				while (!(b % eratostene[l]))
				{
					b /= eratostene[l];
				}
			}
		}
		result = 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;
}