We all know that a prime number is a positive integer that has exactly two distinct positive integer divisors (1 and itself).
For the love of primes one day Kislaya thought of challenging himself and hence he created a problem.
The problem goes, He has positive integers A, A + 1, ..., B (A ≤ B) and he wants to find the minimum window size
L(1 ≤ L ≤ B- A + 1) such that any window starting from X(A ≤ X ≤ B- L+1) among L integers X, X + 1, ..., X + L - 1 there are at least P prime numbers.
Now Kislaya is unable to solve his own problem, Help him solving it.
Find and output the required minimum L. If no value L meets the above mentioned conditions, output -1.

Input
A line containing the number of test cases T (1 ≤ T ≤ 10).
Each of the next T lines contain three space-separated integers A, B, P (1 ≤ A, B, P ≤ 10⁶ and A ≤ B).

Output
In T lines output a single integer ie. the required minimum L for each test case.
If there's no solution, output -1.

Constraints
1 ≤ T ≤ 10
1 ≤ A, B, P ≤ 10⁶
A ≤ B