时间限制： 2.0 秒

空间限制： 512 MB

题目描述

给出一个 $n$ 行 $m$ 列的矩阵，求一个连续子矩阵，使得子矩阵中的数的 GCD（最大公约数）大于 $1$。

问这个子矩阵（的元素个数）最大是多少？

输入格式

从标准输入读入数据。

第一行两个整数 $q , t$。

其中 $q$ 是表示子任务 $1$ 或 $2$。关于子任务的详细说明参见数据规模。$t$ 是测试点数目。

接下来有 $t$ 组数据。每组数据 $n + 1$ 行：

• 第一行两个整数，分别为 $n , m$。
• 接下来 $n$ 行每行 $m$ 个正整数，表示矩阵（第 $i$ 行第 $j$ 列元素为 $a_{i,j}$），用空格隔开。

输出格式

输出到标准输出。

对于每组数据，输出 Case x: y，x 是从 1 开始的测试数据编号，y 是一个整数表示答案。如果没有解，输出 $0$。

1 1
3 3
2 6 8
4 8 3
6 9 4

Case 1: 4

子任务

对于所有数据，$q\in \{1,2\},1\le t\le 5$。

提示

本题输入量较大，请采用效率较高的读入方式。

可以将不同子任务分开处理~