#include<bits/stdc++.h>
using namespace std;
int f(int x){
	for(int i=2;i<=x;i++){
		if(x%i==0){
			return x/i;
		}
	}return 1;
}int lca(int x,int y){
	int cnt=0;
	while(x!=y){
		cnt++;
		if(x>y){
			x=f(x);
		}else{
			y=f(y);
		}
	}return cnt;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	} 
	return 0;
}