#include <iostream>
#include <fstream>

using namespace std;

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

int M,A,B;

int cmmdc(int x, int y){
    if(x==y)
        return x;
    else
        if(x>y)
            return cmmdc(x-y,y);
        else
            return cmmdc(x, y-x);
}

int div(int a, int b){
    int i,nr=0;
    for(i=1;i<=A;i++){
        if(cmmdc(i,b) == 1)
            nr++;
    }
    return nr;
}

void citire(){
    int i;
    in>>M;
    for(i=1;i<=M;i++){
        in>>A>>B;
        out<<div(A,B)<<endl;
    }
}


int main()
{
    citire();

}