{"problem":{"name":"「XSOI-R1」原神数","description":{"content":"原神数 $x$ 需要同时满足以下条件： - $x$ 为质数。 - $x$ 的十进制位两两不同。 比如 $131$ 不是原神数，因为他的百位和个位相等；$42$ 也不是，因为不是质数；$17$ 就是一个原神数。 有 $q$ 次询问，现在要你求出 $l$ 到 $r$ 之间的原神数数量。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10404"},"statements":[{"statement_type":"Markdown","content":"原神数 $x$ 需要同时满足以下条件：\n\n- $x$ 为质数。\n\n- $x$ 的十进制位两两不同。\n\n比如 $131$ 不是原神数，因为他的百位和个位相等；$42$ 也不是，因为不是质数；$17$ 就是一个原神数。\n\n有 $q$ 次询问，现在要你求出 $l$ 到 $r$ 之间的原神数数量。\n\n## Input\n\n第一行一个正整数 $q$。\n\n接下来 $q$ 行每行两个正整数 $l$，$r$。\n\n## Output\n\n$q$ 行 $q$ 个正整数，表示答案。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n在 $100 \\sim 140$ 之间的原神数有 $103,107,109,127,137,139$，共 $6$ 个。\n\n### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n- subtask 0（15 pts）：$1 \\le l \\le r \\le 10^2$。\n\n- subtask 1（15 pts）：$1 \\le l \\le r \\le 10^4$。\n\n- subtask 2（35 pts）：$1 \\le l \\le r \\le 10^7$。\n\n- subtask 3（35 pts）：$1 \\le l \\le r \\le 10^{18}$。\n\n对于所有数据，保证 $1 \\leq l \\leq r \\leq 10^{18}$，$1 \\leq q\\leq 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10404","tags":["洛谷原创","O2优化","素数判断,质数,筛法"],"sample_group":[["4\n45 66\n100 140\n2 90\n114514 1919810","4\n6\n23\n13321"]],"created_at":"2026-03-03 11:09:25"}}