#include <stdio.h>
#include <math.h>
#include <stdlib.h>
unsigned short int *primes;
unsigned short int size;
char is_prime(unsigned int n)
{
unsigned short i, lim, num;
if(n == 1)
return 0;
else if(n <= 3)
return n;
else
{
unsigned short i = 0, lim = sqrt(n), num = primes[i];
while(num && (num <= lim))
{
if(n % num == 0)
{
return 0;
}
i++;
num = primes[i];
}
return 1;
}
}
void populate_primes(unsigned short n)
{
unsigned short num = 7, i = 1, j;
char inc = 2;
primes = (unsigned short *)malloc(sizeof(unsigned short)*n/3);
for(j = 0; j < n/3; j++)
primes[j] = 0;
primes[0] = 5;
while(num <= n)
{
if(is_prime(num))
{
primes[i] = num;
i++;
}
inc = (inc*-1)+6;
num += inc;
}
}
void free_primes()
{
free(primes);
primes = NULL;
}
void print_prime_nos(unsigned int m, unsigned int n)
{
unsigned int num = m;
char inc = 5;
populate_primes(sqrt(n));
while((num <= n) && (num <= 3))
{
if(is_prime(num))
printf("%u\n", num);
num++;
}
if(num <= n)
{
if(num%6 <= 1)
{
num = (num/6*6)+1;
inc = 2;
}
else
{
num = (num/6*6)+5;
inc = 4;
}
}
while(num <= n)
{
if(is_prime(num))
printf("%u\n", num);
inc = (-1*inc)+6;
num += inc;
}
free_primes();
}
int main()
{
unsigned short t;
scanf("%u", &t);
while(t-- > 0)
{
unsigned int m, n;
scanf("%u", &m);
scanf("%u", &n);
print_prime_nos( m, n);
printf("\n");
}
return 0;
}