There is an infinite number of people standing in a line. Let the people be indexed by numbers from $1$ and so on. Also, all people with indices less than or equal to $P$ are important people, all others are unimportant.

Starting from the $2^{nd}$ indexed person, these people start killing others in the line in a pattern. Every important person whose index is $X$, kills all people with indices $X^2, 2 \times X^2, 3 \times X^2$, and so on. Every unimportant person whose index is $X$, kills all people with indices $X, 2 \times X, 3 \times X$, and so on.

Killing happens as follows:

$1$. It starts from the $2^{nd}$ indexed person who kills everyone according to the rule given above.

$2$. The next person with the lowest index, who is yet not killed and whose index is a prime number, starts the same process again and kills everyone according to the rule above.

$3$. Repeat step $2$.

Given an integer $X$, you need to find the index of $X^{th}$ person alive. If there are less than $X$ people alive, print $-1$.

Input:

The first line of input contains a single integer $T$, denoting the number of test cases. Each test case contains $2$ integers $P$ and $X.$

Output:

For each test case, print the index of $X^{th}$ person alive. If there are less than $X$ people alive, print $-1$.

Constraints:

$1 \le T \le 5$

$1 \le P \le 50$

$1 \le X \le 32000$