Counting Prime Sum Pairs

You are given q queries. In each query, you are provided with an integer \( k \). Your task is to count the number of distinct pairs of prime numbers \( (p_1, p_2) \) such that \( p_1 + p_2 = k \), where pairs \( (p_1, p_2) \) and \( (p_2, p_1) \) are considered the same. Use the Sieve of Eratosthenes to generate all prime numbers up to the maximum \( k \) among the queries, and then for each query, determine the number of valid pairs.

Note: A pair is counted only once. For instance, for \( k = 10 \), the valid pairs are \( (3, 7) \) and \( (5, 5) \), so the answer is 2.

inputFormat

The first line contains a single integer \( q \) indicating the number of queries.

The second line contains \( q \) space-separated integers \( k_1, k_2, \dots, k_q \).

It is guaranteed that \( 1 \leq q \leq 10^5 \) and \( 1 \leq k_i \leq 10^6 \).

outputFormat

For each query, output a single line containing the number of distinct pairs of prime numbers whose sum is equal to the given \( k \).

## sample

5
10 26 100 7 12

2
3
6
1
1

</p>