segment seive

#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
typedef pair<ll,ll> pll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
#define fi first
#define se second
#define pb push_back
ll const MOD=1000000007;
#define eb emplace_back
const int N=1e5;
ll a[N+1];
vector<ll>v;
void sieve()
{
  v.pb(2);
  for(ll i=3;i<=N;i+=2)
  {
      if(a[i]==0)
      {
          v.pb(i);
          for(ll j=i+i;j<=N;j+=i)
          {
              a[i]=1;
          }
      }
  }


}
void segment_seive(ll l,ll r)
{

     ll len=r-l+10;
     ll m[len+10];
     memset(m,0,sizeof(m));
     if(l==1)m[0]=1;
     for(ll i=0;v[i]*v[i]<=r;i++)
     {
         // cout<<"base "<<v[i]<<endl;
         ll base=v[i]*v[i];
         if(base<l)base=((v[i]+l-1)/v[i])*v[i];
         for(ll j=base;j<=r;j+=v[i])
         {
             m[j-l]=1;
            // cout<<j<<" ";
         }
     }

         for(ll i=l;i<=r;i++)
        {
         if(m[i-l]==0)cout<<i<<endl;
        }


}
int main()
{
    fastread();
    sieve();

    ll t;
    cin>>t;

    while(t--)
    {
        ll l,r;
        cin>>l>>r;
        segment_seive(l,r);

    }






}