Description

A black-and-white pattern on an $n \times n$ square of tiles is to be transformed into a new square pattern. Write a program to find the minimal method to convert the original pattern into the new one using the following transformations:

• Rotate $90\degree$: Rotate the pattern $90\degree$ clockwise.
• Rotate $180\degree$: Rotate the pattern $180\degree$ clockwise.
• Rotate $270\degree$: Rotate the pattern $270\degree$ clockwise.
• Reflect: Flip the pattern horizontally (mirror over the central vertical line).
• Combination: First reflect horizontally, then apply one of the transformations in $1 \sim 3$.
• No change: The original pattern is unchanged.
• Invalid transformation: The new pattern cannot be obtained by the above methods.

If more than one method works, choose the one with the smallest index.

Use exactly one of the above $7$ steps to accomplish this transformation.

Input Format

The first line contains a positive integer $n$.

Then follow $n$ lines, each containing $n$ characters, all @ or -, representing the initial square.

Then follow another $n$ lines, each containing $n$ characters, all @ or -, representing the target square.

Output Format

A single line containing a number between $1 \sim 7$ (as described above) indicating the transformation method required to convert the original square into the target square.

3
@-@
---
@@-
@-@
@--
--@

1

Hint

Constraints
For $100\%$ of the testdata, $1 \le n \le 10$.

Problem translation from NOCOW.

USACO Training Section 1.2.

Translated by ChatGPT 5