number theory

prime vector 1- 1e7

const int N=1e7;
bool  prime[N+2];
vector<ll>v;
void sieve()
{
      v.pb(2);
      for(ll i=3;i<=N;i+=2)
      {
          if(prime[i]==false)
          {
              v.pb(i);
              for(ll j=i*i;j<=N;j+=(i+i))
              {
                  prime[j]=true;
              }
          }
      }


      //cout<<"total size for "<<N<<"PRIME NUMBER  = "<<v.size()<<endl;
      for(ll i=0;i<v.size();i++)
      {
          // cout<<v[i]<<endl;
      }
}



 /////////////////////////////----------------------////////////////////////



/// 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);

    }






}

///////////////////-----------------------------------////////////////////



divsor count by prime factors  IT WORKS FOR the value 2*N) ( IF N= 6 THEN  1E12 AND IF N=7 THEN N=14)


const int N=1e6;
bool  prime[N+2];
vector<ll>v;
void sieve()
{
      v.pb(2);
      for(ll i=3;i<=N;i+=2)
      {
          if(prime[i]==false)
          {
              v.pb(i);
              for(ll j=i*i;j<=N;j+=(i+i))
              {
                  prime[j]=true;
              }
          }
      }


    //  cout<<"total size for "<<N<<" PRIME NUMBER  = "<<v.size()<<endl;
    //  for(ll i=0;i<v.size();i++)
      {
          // cout<<v[i]<<endl;
      }
}

ll div_counting(ll n)
{
   ll ans=1;

   for(ll i=0;v[i]*v[i]<=n and i<v.size();i++)
   {
       ll cnt=1;
       while(n%v[i]==0)
       {
           n/=v[i];
           cnt++;
       }
       ans*=cnt;
   }

   if(n>1)ans*=2;


   return ans;


}