{"problem":{"name":"[BCSP-X 2024 12 月小学高年级组] 质数补全","description":{"content":"Alice 在纸条上写了一个质数，第二天再看时发现有些地方污损看不清了。 - 在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数称为质数 请你帮助 Alice 补全这个质数，若有多解输出数值最小的，若无解输出 $-1$。 例如纸条上的数字为 $\\tt{1*}$（$\\tt{*}$ 代表看不清的地方），那么这个质数有可能为 $11, 13, 17, 19$，其中最小的为","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4158"},"statements":[{"statement_type":"Markdown","content":"Alice 在纸条上写了一个质数，第二天再看时发现有些地方污损看不清了。\n\n- 在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数称为质数\n\n请你帮助 Alice 补全这个质数，若有多解输出数值最小的，若无解输出 $-1$。\n\n例如纸条上的数字为 $\\tt{1*}$（$\\tt{*}$ 代表看不清的地方），那么这个质数有可能为 $11, 13, 17, 19$，其中最小的为 $11$。\n\n## Input\n\n第一行 $1$ 个整数 $t$，代表有 $t$ 组数据。\n\n接下来 $t$ 行，每行 $1$ 个字符串 $s$ 代表 Alice 的数字，仅包含数字或者 $\\tt{*}$，并且保证首位不是 $\\tt{*}$ 或者 $0$。\n\n## Output\n\n输出 $t$ 行，每行 $1$ 个整数代表最小可能的质数，或者 $-1$ 代表无解。\n\n[samples]\n\n## Note\n\n### 样例 3-6\n\n参考附件中的样例。\n\n### 数据范围\n\n$|s|$ 代表 $s$ 串的长度，对于所有数据，$1 \\leq t \\leq 10, 1 \\leq |s| \\leq 7$，$s$ 中仅包含数字或者 $\\tt{*}$，并且保证首位不是 $\\tt{*}$ 或者 $0$。\n\n本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。\n\n| 子任务编号 | 分值 | $\\mid s\\mid$ | 特殊性质 | 子任务依赖 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $35$ | $\\leq 7$ | $s$ 中没有 $\\tt{*}$ |  |\n| $2$ | $30$ | $\\leq 4$ |  |  |\n| $3$ | $24$ | $\\leq 7$ | $s$ 中至多包含 $1$ 个 $\\tt{*}$ | $1$ |\n| $4$ | $11$ | $\\leq 7$ |  | $1,2,3$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4158","tags":["2024","北京","枚举","深度优先搜索 DFS","筛法","BCSP-X"],"sample_group":[["10\n1*\n3**\n7**\n83*7\n2262\n6**1\n29*7\n889*\n777*\n225*","11\n307\n701\n8317\n-1\n6011\n2917\n8893\n-1\n2251"],["10\n4039***\n2***5*5\n4099961\n25**757\n7***0**\n1***00*\n41811*9\n6***0*7\n8***1**\n6561*59","4039019\n-1\n4099961\n2509757\n7000003\n1000003\n4181129\n6000047\n8000101\n6561259"]],"created_at":"2026-03-03 11:09:25"}}