{"problem":{"name":"[传智杯 #4 初赛] 小卡与质数 2","description":{"content":"小卡最近迷上了质数，所以他想把任何一个数都转化为质数！ 小卡有 $T$ 次询问，每次给你一个数字 $x$，问有多少个比 $x$ 小的非负整数 $y$，使得 $x\\oplus y$ 是质数，其中 $\\oplus$ 表示按位异或。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8842"},"statements":[{"statement_type":"Markdown","content":"小卡最近迷上了质数，所以他想把任何一个数都转化为质数！\n\n小卡有 $T$ 次询问，每次给你一个数字 $x$，问有多少个比 $x$ 小的非负整数 $y$，使得 $x\\oplus y$ 是质数，其中 $\\oplus$ 表示按位异或。\n\n## Input\n\n第一行一个正整数 $T(1\\le T\\le10^5)$，表示有 $T$ 组询问。\n\n接下来 $T$ 行，每行一个正整数 $x(1\\le x\\le 10^6)$。\n\n## Output\n\n对于每组询问，输出一行一个整数，表示答案。\n\n[samples]\n\n## Background\n\n小卡迷上了质数！","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8842","tags":["素数判断,质数,筛法","位运算","传智杯"],"sample_group":[["9\n5\n6\n7\n8\n9\n10\n100\n1000\n10000","2\n4\n4\n2\n2\n4\n22\n163\n1132"]],"created_at":"2026-03-03 11:09:25"}}