#include <iostream>
#include <fstream>

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

int a,b,k;

int cmmdc(int a,int b){
	int c;
	while(b !=0){
		c=a%b;
		a=b;
		b=c;
	
	}
	return a; 
	
}
int main(){
	int t;
	in >>t;
	while(t--){
		in >>a>>b;
for(int i=1;i<=a;i++){
	if(cmmdc(i,b) ==1){
		k++;
	}
}
out <<k<<"\n";
k=0;
	}

}