{"problem":{"name":"[语言月赛 202309] 悬线","description":{"content":"给定一个 $n \\times m$ 的数字阵。约定第 $i$ 行第 $j$ 列上的数用 $(i,j)$ 表示。 我们称以第 $i$ 行第 $j$ 列的格子为底的**悬线**的长度是最大的 $k$，满足 $k \\leq i$ 且 $(i,j), (i-1,j), (i-2,j),\\dots(i-k+1,j)$ 这 $k$ 个数都是**质数**。特别的，如果 $(i, j)$ 本身不是质数，称以第 ","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":"LGB3858"},"statements":[{"statement_type":"Markdown","content":"给定一个 $n \\times m$ 的数字阵。约定第 $i$ 行第 $j$ 列上的数用 $(i,j)$ 表示。\n\n我们称以第 $i$ 行第 $j$ 列的格子为底的**悬线**的长度是最大的 $k$，满足 $k \\leq i$ 且 $(i,j), (i-1,j), (i-2,j),\\dots(i-k+1,j)$ 这 $k$ 个数都是**质数**。特别的，如果 $(i, j)$ 本身不是质数，称以第 $i$ 行第 $j$ 列为底的悬线长度为 $0$。\n\n对于每个格子，请你求出以它为底的悬线长度。\n\n## Input\n\n**本题单个测试点内有多组测试数据**。输入的第一行是一个整数，表示数据组数 $T$。\n\n对每组数据，按如下格式输入：\n\n每组数据第一行是两个整数，表示数字阵的行数 $n$ 和列数 $m$。  \n接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $(i,j)$。\n\n## Output\n\n对每组数据，输出 $n$ 行，每行 $m$ 个用单个空格隔开的整数。第 $i$ 行第 $j$ 个数表示以第 $i$ 行第 $j$ 列的格子为底的悬线长度。\n\n[samples]\n\n## Background\n\n我们定义一个数字是质数，当且仅当它的因子仅有 $1$ 和自身。特别的，$1$ 不是质数。\n\n## Note\n\n### 数据规模与约定\n\n- 对 $20\\%$ 的数据，$n = 1$。\n- 对 $50\\%$ 的数据，$(i,j) \\leq 100$。\n- 对 $80\\%$ 的数据，$(i,j) \\leq 1000$。\n- 对 $100\\%$ 的数据，$1 \\leq n, m \\leq 200$，$1 \\leq (i,j) \\leq 10^5$，$1 \\leq T \\leq 15$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3858","tags":["2023","O2优化","数组","语言月赛"],"sample_group":[["1\n3 3\n1 2 3\n4 5 6\n7 8 9","0 1 1\n0 2 0\n1 0 0"]],"created_at":"2026-03-03 11:09:25"}}