#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int prim(int x,int y){
    while(x!=y){
        if(x>y)
            x-=y;
        else
            y-=x;
    }
    if(x==1 || y==1)
        return 1;
    else
        return 0;

}

int a,b,i,j,n,k;
int main(){
    fin>>n;
    for(j=1;j<=n;j++){
        fin>>a>>b;
        k=0;
        for(i=1;i<=a;i++)
            if(prim(i,b)==1)
                k++;
        fout<<k<<"\n";
    }
    return 0;
}