neither-less-nor-more

All of us have read about factorials and Fibonacci numbers when we started studying algorithms. Today, we will be dealing with the factorials. They are very mystical in the sense that they grow extremely fast. Fortunately, we can study their divisibility properties quite easily.

In the world of factorials we have a function f(N,A) which is the highest exponent of A dividing the factorial of N. Here, N is a nonnegative integer and A is a positive integer greater than 1. For example, f(5,2) = 3 as 2^3 divides 5! = 120 but 2^4 doesn't divide. Also, f(9,3) = 4 because 3^4 divides 9! but no other higher power of 3 divides it. 

We are interested in investigating the function f(N,A) at a greater depth. For a given A, we want to know if there exists an N such that f(N,A) is between L and R, where L and R are the lower and upper bounds i.e., we want to know if there exists an integer N ≥ 0 such that L ≤ f(N,A) ≤ R. If there exists at least one such N, then your job is to output the largest valid candidate for N. Otherwise, output -1.

Input:

The first line of each test file contains a single integer T denoting the number of test cases.
T lines follow each containing 3 space separated integers A, L and R.

Output:

Output T lines each containing a single integer which is the largest N such that L ≤ f(N,A) ≤ R. In case such an N doesn't exist, then output "-1"(without quotes).

Constraints:

1 ≤ T ≤ 1000 
2 ≤ A ≤ 100000000(10^8) 
0 ≤ L ≤ R ≤ 10000000000(10^10) 

It is assured that the result fits in a 64-bit signed integer.

SAMPLE INPUT
2
2 1 1
2 1 2
2 2 2

SAMPLE OUTPUT
3
3
-1

Explanation

In the first case, the result is 3 because f(N,2) = 1 is valid for N = 2, 3. So 3 is the answer.
In the second case, the result is 3 because 1 ≤ f(N,2) ≤ 2 for N = 2, 3. Note that f(4,2) = 3 so 4 doesn't satisfy the constraints.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: