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


int main() {
    
    bool isprime[1000000];
    for(int i=0;i<1000000;i++) isprime[i]=1;
    isprime[0]=0;
    isprime[1]=0;
    
    for(int i=2;i<1000000;i++){
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                isprime[i]=0;
                break;
            }
        }
    }
    
    
    int t;
    cin>>t;
    while(t--){
        int s,e;
        cin>>s>>e;
        
        while(s<e){
            if(isprime[s] && isprime[e]){
                cout<<e-s<<endl;
                break;
            }else if(isprime[s] && !isprime[e]) e--;
            else s++;
        }
        if(s==e) cout<<0<<endl;
    }
    return 0;
}