Description

Many diseases are often caused by genetic mutations. Such mutations arise from a normal DNA sequence through generations of inheritance. In other words, a normal DNA sequence can produce different genetic sequences through various mutations. A fundamental problem in bioinformatics is to determine, for two given DNA sequences, whether one can be produced from the other through a series of genetic mutations.

Let $X = x_1 x_2 \dots x_n$ be a given DNA sequence, where $x_i \in \{A, C, G, T\}$ and $1 \le i \le n$. For $1 \le i \le j \le n$, the substring $X_{i,j} = x_i x_{i+1} \dots x_j$ is called the $[i, j]$ segment of $X$.

Two common types of genetic mutations in a DNA sequence $X = x_1 x_2 \dots x_n$ are chromosomal inversion $\theta$ and chromosomal translocation $\tau$, defined as follows:

1. For a single element: $\theta(A) = T, \theta(T) = A; \theta(C) = G, \theta(G) = C$.
2. For a substring $X_{i,j}$, the chromosomal inversion $\theta_{i,j}(X)$ is defined as: $\theta_{i,j}(X) = \theta(x_j) \theta(x_{j-1}) \dots \theta(x_i)$.
3. For substrings $X_{i,j}$ and $X_{k,l}$ where $1 \le i < k \le j \le n$, the chromosomal translocation $\tau_{i,j,k}(X)$ is defined as: $\tau_{i,j,k}(X) = x_k \dots x_j x_i \dots x_{k-1}$.

Two mutations are said to be disjoint if their segments do not overlap. Let $\Theta$ be a set of disjoint genetic mutations, and $X = x_1 x_2 \dots x_n$ be a given DNA sequence. The DNA sequence obtained by applying the mutations in $\Theta$ to $X$ in sequence is denoted as $\Theta(X)$. For example, when $X = TAGAC$ and $\Theta = \{\tau_{1,2}, \theta_{5,5}\}$, $\Theta(X) = AGTAG$.

For two DNA sequences $X$ and $Y$ of the same length, if there exists a set of disjoint genetic mutations $\Theta$ such that $\Theta(X) = Y$, then $X$ is said to be mutable to $Y$. The minimum number of disjoint mutations is called the mutation distance between $X$ and $Y$, denoted as $md(X, Y)$. When $X$ is not mutable to $Y$, $md(X, Y) = \infty$.

For example, when $X = TAGAC$ and $Y = TAACG$, $\Theta_1 = \{\theta_{1,2}, \tau_{3,5,4}\}$ and $\Theta_2 = \{\tau_{3,5,4}\}$ are the only two sets of disjoint mutations such that $\Theta_1(X) = Y$ and $\Theta_2(X) = Y$. Therefore, $md(X, Y) = |\Theta_2| = 1$.

The genetic mutation problem requires calculating the mutation distance $md(X, Y)$ for two given DNA sequences $X$ and $Y$ of the same length.

Input

The first line contains a positive integer $n$ ($1 \le n \le 23000$), representing the length of the DNA sequences. The next two lines provide the input sequences $X = x_1 x_2 \dots x_n$ and $Y = y_1 y_2 \dots y_n$, respectively. Each element in the sequences is a character from $\{A, C, G, T\}$.

Output

Output the calculated mutation distance $md(X, Y)$. If $md(X, Y) = \infty$, output -1.

Examples

Input 1

5
TAGAC
TAACG

Output 1

1