#include<iostream>
#include<math.h>
using namespace std;
bool check_prime(int num)
{
	int temp;
	int i=6;
	temp= sqrt((float)num);
	while((i-1)<=temp)
	{
	if(num%(i-1)==0) return (i-1);
	if(num%(i+1)==0) return (i-1);
	i+=6;
	}
	return true;
}
int main()
{
	int num_test, m, n;
	int i = 0, j = 0;
	scanf("%d", &num_test);
	for (i = 0;i < num_test;i++)
	{
		scanf("%d", &m);
		scanf("%d", &n);
		if(m<2) m=2;
		for (j = m;j <= n;j++)
		{
			if(j==2||j==3)
			{
			printf("%d \n", j);
			return 0;
			}
		if(j%2==0||j%3==0) return 0;
		if (check_prime(j) == true)
				printf("%d \n", j);
		}
		printf("\n");
	}
	return 0;
}