题解

#include<bits/stdc++.h>
using namespace std;

int q;

int solve(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0) return x/i;
	}
	return 1; //x为1或x为质数
}

int main(){
	cin>>q;
	
	while(q--){
		int x1,y1,res=0;
		
		cin>>x1>>y1;
		
		while(1){
			if(x1>y1){
				res++;
				x1=solve(x1); //x1往上找父节点
			}else if(x1<y1){
				res++;
				y1=solve(y1); //y1往上找父节点
			}else{ //一致了输出统计的路径长度
				cout<<res<<'\n';
				break;
			}
		}
	}
	
	return 0;
}