题目描述

Dr. X 研制的间谍卫星拍摄到了许多 U 国建筑的照片。为了找出其中的军事设施，Dr. X 需要估算建筑的大小。Dr. X 发现，所有间谍卫星拍摄的照片都恰好包含一个完整的正方形，其中建筑边界上的像素被标记为了白色（用 $1$ 表示），其余像素被标记为了黑色（用 $0$ 表示）。一些照片的案例如下：

你的任务是根据拍摄的照片估算被摄正方形的边长 (米)。照片中的每个像素都代表一个一米乘一米的正方形。

输入格式

输入数据第一行包含一个整数 $n$，代表间谍卫星拍摄照片的数量，随后是 $n$ 张照片，其中每张照片 $128$ 行，每行 $128$ 个字符，$1$ 表示白色，$0$ 表示黑色。两张照片之间有一个空行。

输出格式

为每张照片输出一个整数或小数，代表估计的正方形边长。输入数据保证每张照片中都恰好只包含一个正方形，且正方形的边界完全在照片内。

见附件中的 sample.in

53

提示

本题仅有一个 $n\leq 100$ 的测试数据，且测试数据和样例数据的生成方式相同。

当你对一幅照片估计的边长和实际建筑边长差距不超过 $2$ 时，则认为估计正确。若估计正确的照片比例 $A > 0.5$，本题得分为 $(A − 0.5) \times 30$ 向下取整，否则得零分。

我们在生成每张照片时，都先在平面上生成一个随机的、边长为整数、边界宽度为 $1$ 像素的正方形，然后“拍摄”得到它的照片。

本题原始满分为 $15\text{pts}$。