{"raw_statement":[{"iden":"background","content":"小卡迷上了质数！"},{"iden":"statement","content":"小卡最近迷上了质数，所以他想把任何一个数都转化为质数！\n\n小卡有 $T$ 次询问，每次给你一个数字 $x$，问有多少个比 $x$ 小的非负整数 $y$，使得 $x\\oplus y$ 是质数，其中 $\\oplus$ 表示按位异或。"},{"iden":"input","content":"第一行一个正整数 $T(1\\le T\\le10^5)$，表示有 $T$ 组询问。\n\n接下来 $T$ 行，每行一个正整数 $x(1\\le x\\le 10^6)$。"},{"iden":"output","content":"对于每组询问，输出一行一个整数，表示答案。"}],"translated_statement":null,"sample_group":[["9\n5\n6\n7\n8\n9\n10\n100\n1000\n10000","2\n4\n4\n2\n2\n4\n22\n163\n1132"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}