Lonely Divisor
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
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.
Output
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.
Sample
| 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.
