#include<bits/stdc++.h>
using namespace std;
int n;
int jkl(int y){
for(int i=2;i<=sqrt(y);i++){
if(y%i==0) return y/i;
}
return 1;
}
int dfs(int l,int r){
int sum=0;
while(l!=r){
if(l<r){
r=jkl(r);
}else{
l=jkl(l);
}
sum++;
}//人口结构v
return sum;
}
int main(){
cin>>n;//n
while(n--){
int l,r;
cin>>l>>r;
cout<<dfs(l,r)<<endl;
}
return 0;
}
