Limak is a little bear who loves school. Today was his first lesson in cryptography, and the teacher assigned some difficult homework—to find any number with exactly $\mbox{K}$ divisors. Limak wants to go the extra mile and find the biggest possible number; however, his teacher explained that there are arbitrarily large numbers with this property.

To give this little bear a more achievable challenge, the teacher advised him to consider only numbers not greater than $N$.

Given $N$ and $\mbox{K}$, what is the largest number Limak can find?

Input Format

The first line contains an integer, ${T}$ (the number of test cases).

The ${T}$ subsequent lines of test cases each contain two space-separated integers, $N$ and ${K}$, respectively.

Constraints

$1\leq T\leq50$
$1\leq N\leq10^{12}$
$1\leq K\leq40$

Output Format

For each test case, print the biggest number Limak can find on a new line. Print $-1$ if no such number exists.

Sample Input
3
15 3
15 4
15 5

Sample Output
9
15
-1

Explanation

As each test case uses $N=15$, here are the numbers ranging from ${1}$ to $N$ and their divisors:

$15$ is evenly divisible by $4$ numbers (${1}$, $3$, $5$, and $15$).

${14}$ is evenly divisible by ${4}$ numbers (${1}$, $2$, $7$, and ${14}$).

$13$ is evenly divisible by $2$ numbers (${1}$ and $13$).

$12$ is evenly divisible by ${6}$ numbers (${1}$, $2$, $3$, ${4}$, ${6}$, and $12$).

${11}$ is evenly divisible by $2$ numbers (${1}$ and ${11}$).

$10$ is evenly divisible by ${4}$ numbers (${1}$, $2$, $5$, and $10$).

${9}$ is evenly divisible by $3$ numbers (${1}$, $3$, and ${9}$).

$8$ is evenly divisible by ${4}$ numbers (${1}$, $2$, ${4}$, and $8$).

$7$ is evenly divisible by $2$ numbers (${1}$ and $7$).

${6}$ is evenly divisible by $3$ numbers (${1}$, $2$, and $3$).

$5$ is evenly divisible by $2$ numbers (${1}$ and $5$).

${4}$ is evenly divisible by $3$ numbers (${1}$, $2$, and ${4}$).

$3$ is evenly divisible by $2$ numbers (${1}$ and $3$).

$2$ is evenly divisible by $2$ numbers (${1}$ and $2$).

${1}$ is only evenly divisible by ${1}$ number (${1}$).

Test Case 0:

We must find the largest number $\leq15$ having exactly $3$ divisors. Because ${9}$ is the largest number $\leq15$ having exactly $3$ divisors, we print ${9}$ on a new line.

Test Case 1:

We must find the largest number $\leq15$ having exactly ${4}$ divisors. Because $15$ is the largest number in the list above having exactly ${4}$ divisors, we print $15$ on a new line.

Test Case 2:

There is no number between ${1}$ and $15$ having exactly $5$ divisors, so we print $-1$ on a new line.

见题面

见题面