题目描述

Blue Mary 需要判断两张 $n \times n$ 的战役地图是否属于同一类。地图编码为 $n \times n$ 的矩阵，每个格子是一个 32 位有符号正整数。

两个矩阵的相似程度定义为它们的最大公共正方形子矩阵的边长。

输入格式

• 第一行：正整数 $n$
• 接下来 $n$ 行：第一张地图的矩阵
• 再接下来 $n$ 行：第二张地图的矩阵

输出格式

一个正整数，表示两个矩阵的相似程度（最大公共正方形子矩阵边长）

样例

输入

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

输出

2

解释：两个地图的最大公共正方形子矩阵为：

数据范围与提示

对于 $100\%$ 的数据，$n \leq 50$。