Chotu being over confident about his programming skills is challenging everyone that he can solve any problem. Seeing chotu's over confidence his rival decided to test him by giving him the following problem.
You are given a range [A, B] where A <= B, find the minimum number L such that any consecutive L numbers in that range have atleast K primes.
But now Chotu is finding this problem difficult for him. Help Chotu to solve the problem.
Input
First line contains an integer T denoting number of test cases.
Next T lines contain three integers A, B and K respectively.
Output
For each test case print the minimum value of L. If there is no solution than print -1.
Constraints
1 <= T <= 10
1 <= A <= B <= 106
1 <= K <= 106
In Test Case 1:
A = 3, B = 5 and K = 1 therefore value of L can vary from 1 to 3 (5-3+1).
If L is 1 than there will be three ranges (3,3) , (4,4) and (5,5) and in each range there should be atleast 1 prime number. Since in range (4,4) there is no prime number hence L cannot be eqaul to 1.
If L is 2 than there will be two ranges (3,4) and (4,5) and in each range there is exactly 1 prime number. Hence L can be equal to 2.
If L is 3 than there is only a single range (3,5) and in this range there are 2 prime numbers hence L can also be equal to 3.
Since we require minimum value of L hence output is 2.
