#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
typedef vector<ll> vll;
#define pb              push_back 
#define fori(n)         for (ll i=0; i<n; i++) 
#define forj(n)         for (ll j=0; j<n; j++) 
#define fork(n)         for (ll k=0; k<n; k++) 
#define forn(n)         for (ll i=1; i<=n; i++) 
#define forn2(n)        for (ll j=1; j<=n; j++) 
#define forn3(n)        for (ll k=1; k<=n; k++) 
#define Sort(a)         sort(a.begin(),a.end())

vll primes;

void solve(){

    ll n;
    cin>>n;
    ll u=1e7+2;
    ll p=sqrtl(u);
    fori(n){
        ll x,y;
        cin>>x>>y;
        if(y-x==1){
            cout<<-1<<endl;
            continue;
        }
        // if(y-x==1&&y==2){
        //     cout<<0<<endl;
        //     continue;
        // }
        ll k=y-x;
        ll ans=100000000;
        for(auto it:primes){
            if(it>k){
                break;
            }
            if(k%it==0){
                ans=min(ans,(it-y%it)%it);
                while(k%it==0){
                    k/=it;
                }

            }

        }
        if(k>p){
            ans=min(ans,(k-y%k)%k);
        }
        cout<<ans<<endl;



    }




}

int main(){


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     int N = 1e4+10;
        vector <ll> isprime(N,1) , hp(N,0),lp(N,0);
        isprime[0] = isprime[1] = 0;
        for(int i=2;i*i<=N;i++)
        {
            if(isprime[i]==1)
            {
                
                for(int j=2;j*i<=N;j++)
                {
                    isprime[i*j]=0;
                                    }
            }
        }
        ll y=1e7+2;
        ll k=sqrtl(y);
        forn(k){
            if(isprime[i])primes.pb(i);
        }
    //Redeem yourself King.
    solve();
    
   
    return 0;
}