Suspended Line in a Prime Grid

You are given an \( n \times m \) grid of integers. The number in row \( i \) and column \( j \) is denoted by \( (i,j) \). We define the suspended line with base at cell \( (i,j) \) as the maximum integer \( k \) such that \( k \le i \) and the \( k \) numbers \( (i,j),\,(i-1,j),\,(i-2,j),\,\dots,\,(i-k+1,j) \) are all prime numbers. In particular, if the cell \( (i,j) \) itself is not a prime, then the suspended line length in that cell is 0. For each cell in the grid, you are to compute the length of the suspended line with the cell as its base.

inputFormat

The first line contains two integers \( n \) and \( m \) separated by a space. The following \( n \) lines each contain \( m \) integers representing the grid.

outputFormat

Output \( n \) lines, each containing \( m \) integers. The \( j \)-th number in the \( i \)-th line is the length of the suspended line whose base is cell \( (i,j) \). Separate numbers by a single space.

sample

3 3
2 3 5
3 4 7
11 2 3

1 1 1
2 0 2
3 1 3