Let num(num >= 0) is a positive integer or zero. We can represent num in the following two forms if it is possible to do so -
1. num = n² + 2 * n, for non-negative integer n
2. num = m² - 2 * m, for non-negative integer m

Suppose there is num that can be represented in both the forms. Consider this type of number as a magic number. Consider the following 5 cases -
1. n is the only prime.
2. m is the only prime.
3. n and m both are primes.
4. n is prime.
5. m is prime.

Input

First line of input is t, total number of test cases. For each test case the first line is q, total number of queries. Then there will be (2 * q) lines. First line contains c (referring to case mentioned in the problem description) and second line contains two integers a and b defining the range [a, b] for magic number.
t < 1001
q < 5001
0 < c < 6
minimum_value_of_a = 0
maximum_value_of_b = 10⁶

Output

For every test case, that has q queries, the output has (q + 1) lines. First line will be simply printing the test case number and then q lines will be printing total number of magic numbers in the given range [a, b] under the specific case mentioned in input.

Example

Input:
2
3
1
5 20
2
1 30
3
10 18
2
4
1 10
5
1 10

Output:
Test Case :#1:
Query :#1: 1
Query :#2: 1
Query :#3: 1
Test Case :#2:
Query :#1: 1
Query :#2: 1