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.