#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 cmmdc(int a , int b)
{
	int  r;
	while ( b != 0 )
	{
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}
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];
    for (int i = 0; i < m; i++)
    {
		fscanf(f, "%d %d", &v[i].a, &v[i].b);
    }
	for (int j = 0; j < m; j++)
	{
		int nr = 0;
		for (int i = 1; i <= v[j].a; i++)
			if (cmmdc(i, v[j].b) == 1)
			{
				nr++;
			}
		
		fprintf(g, "%d\n", nr);
	}
    fclose(f); fclose(g);
    return 0;
}