Problem Description

Jodie slowly enters the laboratory, with the spirit Aiden by her side, who seems a bit unhappy but still follows her closely.

Today, Jodie is conducting an experiment on a very large circular ring, which has $L$ grids, each displaying a lowercase English letter. Jodie starts from any grid, and when she leaves a grid, the letter on it changes randomly, and no one knows what it will become. Jodie walks clockwise on this ring without looking back, and each time she enters a grid, she writes down the letter currently displayed on it in her notebook. Since Jodie cannot look back and does not know how many grids are on the ring, she does not know when she will reach a repeated point, so she asks Aiden to remind her when she steps into a repeated grid. However, due to a possible conflict, Aiden gets angry and decides to tell her only after she has walked $K$ ($K \geq 0$) steps into repeated grids. Jodie conducts two experiments and records the paths taken in each. Before the second experiment, the letters on each grid are reset to their state at the beginning of the first experiment. Jodie discovers Aiden's prank and can only inform the experimenters of the maximum possible $L$.

To help you better understand the problem, please analyze the following example carefully:

Suppose $L = 4$, $K = 1$

The letters displayed on the grids before the first experiment are as follows:

Jodie starts from the grid displaying the letter a, and Aiden tells her to stop after she has walked $K$ steps into repeated grids, so Jodie walks a total of $5$ steps. The changes in the grids with each step are as follows (the arrow indicates the grid Jodie is on):

In the second experiment, Jodie starts from the grid displaying the letter c, and the changes in the grids with each step are as follows (the arrow indicates the grid Jodie is on):

The paths recorded by Jodie in the two experiments are:

abcdx

cdabz

Given the lengths $N$ of the paths recorded by Jodie and the contents she wrote down, but without knowing the value of $K$, you are asked to help find the maximum possible $L$.

Input Format

The first line contains an integer $N$.

The second line contains a string of length $N$ consisting only of lowercase letters.

The third line contains a string of length $N$ consisting only of lowercase letters.

Output Format

Output a single number $L$, representing the maximum possible number of grids on the ring.

Sample Input and Output

Sample Input #1

5
abcdx
cdabz

Sample Output #1

4

Sample Input #2

4
abcd
cdab

Sample Output #2

4

Notes

For $20\%$ of the data, $1 \leq N \leq 5,000$

For $50\%$ of the data, $1 \leq N \leq 600,000$

For $100\%$ of the data, $1 \leq N \leq 2,000,000$

见题面 Input 部分

见题面 Output 部分