SP16062 SNGCP - Count Primes

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} $ + 2 \* n, for non-negative integer n** **2.** **num = m $ ^{2} $ - 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.**

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 $ ^{6} $**

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.