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$$