XOR Prime Queries

Little Ka recently became fascinated with prime numbers, and he wants to transform any number into a prime number! You are given $T$ queries. For each query, a number $x$ is provided. Your task is to count how many non-negative integers $y$ (with $0 \le y < x$) satisfy that $x \oplus y$ is a prime number, where $\oplus$ denotes the bitwise XOR operation. A number $p$ is considered prime if it is greater than 1 and has no divisors other than 1 and itself.

For example, if $x=5$, then the possible values of $y$ are 0, 1, 2, 3, and 4. Evaluating $5 \oplus y$, we obtain 5, 4, 7, 6, and 1 respectively; among these, 5 and 7 are prime numbers, so the answer is 2.

inputFormat

The first line contains an integer $T$, the number of queries. Each of the following $T$ lines contains an integer $x$.

outputFormat

Output $T$ lines, each containing the count of non-negative integers $y$ (with $0 \le y < x$) such that $x \oplus y$ is a prime number.

sample

1
5

2