#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,x,y,a[N],b[N];
int primes[N],cnt;
bool st[N];
void get_primes(int n){//线性筛法求质数 
	for(int i=2;i<=n;i++){
		if(!st[i]) primes[cnt++]=i;
		for(int j=0;primes[j]<=n/i;j++){
			st[primes[j]*i]=1;
			if(i%primes[j]==0) break;
		}
	}
}
int main(){
	int T=1;
	cin>>T;
	get_primes(1e6);
	while(T--){
		cin>>x>>y;
		if(x>y) swap(x,y);
		if(__gcd(x,y)!=1){
			cout<<0<<endl;
			continue;
		}		
		if(x==y-1){
			cout<<-1<<endl;
			continue;
		}
		int m=y-x;// y+k=nd,x+k=md --> y-x=(n-m)*d 
		//y-x=一个正整数*d 时成立 
		vector<int> v;
		for(int i=0;primes[i]*primes[i]<=m&&i<cnt;i++){
			int j=primes[i];
			if(m%j==0){
				while(m%j==0) m/=j;
				v.push_back(j);
			}
		}
		if(m>1) v.push_back(m);
		int ans=y-x;
		ans=min(ans,v[0]-x%v[0]);
		cout<<ans<<endl;
	}
	return 0;
}