Maximum Ring Size

Jodie performs two experiments on a circular ring with L cells. Initially, every cell displays a lowercase English letter. The ring has L cells arranged in a circle according to some initial configuration \(S\) (\(S\) is a string of length \(L\)). In each experiment, Jodie starts from an arbitrary cell and walks clockwise. Each time she enters a cell, she records the letter currently displayed on that cell. As soon as she leaves a cell, its letter changes randomly to some unknown lowercase letter.

Because she cannot go backward and does not know the number of cells \(L\), she may eventually step into a cell that she has visited before. To warn her before she repeats a cell, her spirit companion Aiden is supposed to caution her. However, Aiden (in a bad mood) delays the warning and only alerts her after she has taken \(K\) (\(K \ge 0\)) steps following the first repetition.

Thus, in each experiment, Jodie walks a total of \(N = L + K\) steps. Note that the first \(L\) letters recorded come from the cells in their initial state, and they represent a cyclic shift of the initial configuration \(S\). Specifically, if in the first experiment she starts at some index, the first \(L\) recorded letters are a cyclic permutation of \(S\); in the second experiment, she may start at a different index so that the first \(L\) letters form another cyclic permutation of \(S\>.

Your task is: given the two recorded paths (each a string of length \(N\)) from the experiments, determine the maximum possible \(L\) (i.e. the maximum ring size) that can be consistent with these recordings.

Hint: Let the two recorded strings be X and Y. For some \(L\) (with \(1 \le L \le N\)) and an integer offset \(r\) (with \(0 \le r < L\)), the first experiment shows X[0...L-1] and the second shows Y[0...L-1]. These must be cyclic rotations of the same string \(S\). Notice that \(Y[0...L-1]\) is a rotation of \(X[0...L-1]\) if and only if Y[0...L-1] appears as a substring in X[0...L-1] + X[0...L-1] (where '+' denotes string concatenation).

inputFormat

The first line contains an integer \(N\) (the length of the recorded path, where \(N = L + K\)).

The second line contains a string of length \(N\) representing the recorded path in the first experiment.

The third line contains a string of length \(N\) representing the recorded path in the second experiment.

outputFormat

Output a single integer, the maximum possible \(L\) (the number of cells on the ring) such that the first \(L\) letters of the two experiments are cyclic rotations of each other.

sample

5
abcdx
cdabz

4