# include <bits/stdc++.h>

using namespace std;
int q,x,y;
int fa(int k){
	for(int i = 2;i*i<=k;i++)
		if(k%i==0)
			return k/i;
	return 1;
}
int lca(int x,int y){
	int ans=0;
	while(x!=y){
		if(x<y)y=fa(y);
		else x=fa(x);
		ans++;
	}
	return ans;
}
int main(){
	cin>>q;
	while(q--){
		cin>>x>>y;
		cout<<lca(x,y)<<'\n';
	}
	return 0;
}