Limits
3s, 512 MB

Given a positive integer `$N$`

you have to find it’s lonely divisor. The question is what is **Lonely Divisor**, right? A lonely divisor of `$N$`

is the only divisor which has exactly `$K$`

divisors. If there are more than one divisor having exactly `$K$`

divisors then they are not lonely.

Initially I told you that I will give you a positive integer `$N$`

and you have to find it’s lonely divisor. But I have changed my mind. Instead of giving you a number I will give you a range `$[L, R]$`

and a positive integer `$K$`

. You have to find the number in range `$[L, R]$`

**inclusively** which has the **largest Lonely Divisor**. Note that Lonely Divisor must have exactly `$K$`

divisors.

If there are many solutions just choose the largest number. If there are no solution then just print `$-1$`

.

Input will start with a positive integer `$T$`

`$(T \leq 10^6)$`

denoting the number of test cases. Each test case will have three positive integer `$L, R$`

`$(1 \leq L \leq R \leq 10^5)$`

denoting the range and `$K$`

`$(1 \leq K \leq 128)$`

.

**Use faster I/O as the input will be large**.

For each test case print the number with the **largest lonely divisor** followed by a space, followed by the lonely divisor.

Note that if there are many solutions you have to print the largest number. In case if there is no solution just print `$-1$`

. Also look at the sample I/O for better understanding.

Input | Output |
---|---|

3 1 6 2 1 8 3 1 10 5 | 5 5 8 4 -1 |

** $1st \; Case$:** There are

`$3$`

integers `$2, 3$`

and `$5$`

which have a lonely divisor having exactly `$2$`

divisors. `$5$`

has the largest lonely divisor which is `$5$`

. So the answer is `$5$`

. Note that `$6$`

also has `$2$`

and `$3$`

as its divisor and they have exactly `$2$`

divisors. But they are not lonely.** $2nd \; Case$:** In that range only

`$4$`

has `$3$`

divisors. Now `$4$`

is not only a divisor of itself but also a divisor of `$8$`

. And both `$4$`

and `$8$`

have only one divisor which has exactly `$3$`

divisors. So possible answer is either `$4$`

or `$8$`

. As we have more than one solution we need choose the largest one. So the answer is `$8$`

.** $3rd \; Case$:** There is no number in that range has

`$5$`

divisors.