[传智杯 #4 初赛] 小卡与质数 2

小卡迷上了质数！

小卡最近迷上了质数，所以他想把任何一个数都转化为质数！ 小卡有 $T$ 次询问，每次给你一个数字 $x$，问有多少个比 $x$ 小的非负整数 $y$，使得 $x\oplus y$ 是质数，其中 $\oplus$ 表示按位异或。

第一行一个正整数 $T(1\le T\le10^5)$，表示有 $T$ 组询问。 接下来 $T$ 行，每行一个正整数 $x(1\le x\le 10^6)$。

对于每组询问，输出一行一个整数，表示答案。

9
5
6
7
8
9
10
100
1000
10000

2
4
4
2
2
4
22
163
1132