You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

我们定义一个数字是质数，当且仅当它的因子仅有 $1$ 和自身。特别的，$1$ 不是质数。

题目描述

给定一个 $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)$ 本身不是质数，称以第 $i$ 行第 $j$ 列为底的悬线长度为 $0$。

对于每个格子，请你求出以它为底的悬线长度。

输入格式

本题单个测试点内有多组测试数据。输入的第一行是一个整数，表示数据组数 $T$。

对每组数据，按如下格式输入：

每组数据第一行是两个整数，表示数字阵的行数 $n$ 和列数 $m$。
接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $(i,j)$。

输出格式

对每组数据，输出 $n$ 行，每行 $m$ 个用单个空格隔开的整数。第 $i$ 行第 $j$ 个数表示以第 $i$ 行第 $j$ 列的格子为底的悬线长度。

1
3 3
1 2 3
4 5 6
7 8 9

0 1 1
0 2 0
1 0 0

提示

数据规模与约定

• 对 $20\%$ 的数据，$n = 1$。
• 对 $50\%$ 的数据，$(i,j) \leq 100$。
• 对 $80\%$ 的数据，$(i,j) \leq 1000$。
• 对 $100\%$ 的数据，$1 \leq n, m \leq 200$，$1 \leq (i,j) \leq 10^5$，$1 \leq T \leq 15$。