#include<stdio.h>

#include<iostream>
#include<fstream>

using namespace std;

#define MAXPRIME 1000000

int M;
long long A,B;

long long cmmdc(long long a,long long b){
	long long r;
	do{
		r=a%b;
		a=b;
		b=r;
	}while(r>0);
	return a;
}

int main(){
	
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	scanf("%d",&M);

	for(int i=0;i<M;i++){
		scanf("%lld %lld", &A, &B);
		long long nb=0;
		for(int i=1;i<=A;i++){
			if(cmmdc(i,B)==1)
				nb++;
		}
		printf("%lld\n",nb);
	}

	return 0;
}