Background

Xiaoka has become obsessed with prime numbers!

Problem Description

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.

Input Format

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)$.

Output Format

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

9
5
6
7
8
9
10
100
1000
10000

2
4
4
2
2
4
22
163
1132

Hint

Translated by ChatGPT 5