Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Lonely Divisor

By rumman13 · Limits 3s, 512 MB

Given a positive integer NN you have to find it’s lonely divisor. The question is what is Lonely Divisor, right? A lonely divisor of NN is the only divisor which has exactly KK divisors. If there are more than one divisor having exactly KK divisors then they are not lonely.

Initially I told you that I will give you a positive integer NN 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][L, R] and a positive integer KK. You have to find the number in range [L,R][L, R] inclusively which has the largest Lonely Divisor. Note that Lonely Divisor must have exactly KK divisors.

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

Input

Input will start with a positive integer TT (T106)(T \leq 10^6) denoting the number of test cases. Each test case will have three positive integer L,RL, R (1LR105)(1 \leq L \leq R \leq 10^5) denoting the range and KK (1K128)(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-1. Also look at the sample I/O for better understanding.

Sample

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

1st  Case1st \; Case: There are 33 integers 2,32, 3 and 55 which have a lonely divisor having exactly 22 divisors. 55 has the largest lonely divisor which is 55. So the answer is 55. Note that 66 also has 22 and 33 as its divisor and they have exactly 22 divisors. But they are not lonely.

2nd  Case2nd \; Case: In that range only 44 has 33 divisors. Now 44 is not only a divisor of itself but also a divisor of 88. And both 44 and 88 have only one divisor which has exactly 33 divisors. So possible answer is either 44 or 88. As we have more than one solution we need choose the largest one. So the answer is 88.

3rd  Case3rd \; Case: There is no number in that range has 55 divisors.

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.