题目描述

在给定的 $m * n$ 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；

值 1 代表新鲜橘子；

值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入格式

第一行一个数$t$表示询问组数

第二行开始每组数先是$m,n$($m,n$代表网格的长和宽)，接着$m$行$n$列数，空格隔开。

输出格式

t个数，表示最小分钟数,每个数占一行。

样例 #1

样例输入 #1

2
3 3 
2 1 1
1 1 0
0 1 1
3 3
2 1 1
0 1 1
1 0 1

样例输出 #1

4
-1

提示

$1<=t<=20$

$1 <= m, n <= 1000$