Description

Blue Mary has recently become hooked on playing StarCraft RPGs. She is trying to find more campaign maps to further improve her skills.

Since Blue Mary has reached a certain skill level, for campaign maps that can be cleared using the same strategy, she only needs to play one of them to learn that type of strategy, and then she loses interest in other maps of the same type. Many maps circulating online share the same strategy, so Blue Mary needs you to write a program to help her determine which maps belong to the same type.

Specifically, Blue Mary has encoded each campaign map as an $n \times n$ matrix, where each cell contains a positive 32-bit (signed) integer. For two matrices, their similarity is defined as the side length of their largest common square submatrix. The greater the similarity between two matrices, the more likely the two campaign maps are of the same type.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain $n$ positive integers, representing the matrix of the first campaign map.

The following $n$ lines each contain $n$ positive integers, representing the matrix of the second campaign map.

Output Format

Output a single line containing one positive integer, which is the similarity between the two matrices.

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

2

Hint

Sample explanation:

Submatrix: $\begin{bmatrix} 5 & 6 \\ 8 & 9 \\ \end{bmatrix}$ is the largest common submatrix of the two maps.

Constraints: $n \le 50$.

Translated by ChatGPT 5