# include <fstream>
 # include <algorithm>
 # include <vector>
 
 using namespace std;
 
 ifstream f ("pinex.in");
 ofstream g ("pinex.out");
 
 long long n, a, b, sol;
 
 int cmmdc(int x, int y)
{
    int r = x % y;
	
    while( r )
    {
        x = y;
        y = r;
        r = x % y;
    }
     
    return y;
}

int main()
{
	int i, j;
	f >> n;
	for ( i = 1 ; i <= n ; i++ )
	{
		sol = 0;
		f >> a >> b;
		for ( j = 1 ; j <= a ; j++ )
			if ( cmmdc( j, b) == 1 )
				sol ++;
			g << sol <<"\n";
	}
}