P8842 [ChuanZhi Cup #4 Preliminary] Xiaoka and Primes 2

Xiaoka has become obsessed with prime numbers!

Xiaoka has recently become obsessed with prime numbers, so he wants to turn any number into a prime number! Xiaoka has $T$ queries. Each time, you are given a number $x$. You need to ask: how many non-negative integers $y$ less than $x$ make $x \oplus y$ a prime number, where $\oplus$ denotes bitwise XOR.

The first line contains a positive integer $T$ $(1 \le T \le 10^5)$, meaning there are $T$ queries. The next $T$ lines each contain a positive integer $x$ $(1 \le x \le 10^6)$.

For each query, output one line with one integer, representing the answer.

Translated by ChatGPT 5