Counting Prime Pairs

You are given (T) test cases. For each test case, an integer (N) is provided. Your task is to count the number of distinct pairs of prime numbers ((p, q)) such that (p + q = N) and (p \leq q).

For instance, when (N = 10), the valid pairs are ((3, 7)) and ((5, 5)), hence the answer is 2.

The solution typically involves using the Sieve of Eratosthenes to identify prime numbers and then counting the valid pairs.

inputFormat

The first line of input contains a single integer (T), representing the number of test cases. Each of the following (T) lines contains a single integer (N).

outputFormat

For each test case, output a single line containing the number of distinct prime pairs ((p, q)) such that (p + q = N) and (p \leq q).## sample

2
10
12

2
1