Distinct Prime Pairs

Given an integer x, determine the number of distinct pairs of prime numbers \(a\) and \(b\) such that \(a+b=x\). A pair \((a, b)\) is considered the same as \((b, a)\). You are given multiple queries and for each query you need to output the count of such prime pairs.

For example, for x = 10, the valid prime pairs are \((3, 7)\) and \((5, 5)\), so the answer is 2.

inputFormat

The first line contains an integer Q, the number of queries. Each of the next Q lines contains an integer x ((2 \le x \le 10^4)). Input is read from standard input (stdin).

outputFormat

For each query, output the count of distinct prime pairs on a new line. Output is written to standard output (stdout).## sample

3
10
6
8

2
1
1