밍구 ha desarrollado la aplicación de chat de última generación ChatChatA.

Después de distribuir ChatChatA, ¡un informe de error crítico llegó a 밍구! Durante el proceso de escribir un mensaje, cuando el último carácter del mensaje es un carácter específico y se ingresa otro carácter específico, ¡el mensaje se "duplica"!

Explicando con precisión, "duplicarse" significa lo siguiente:

• Sea $M$ el mensaje que se está escribiendo actualmente, $s$ el último carácter de $M$, y $c$ el carácter que se va a ingresar.
• Sea $D$ el conjunto de pares $(s, c)$ que hacen que el mensaje se "duplique".
  • Si $(s, c) \in D$, al ingresar $c$, $M$ se convierte en $M + M + c$, ¡no en $M + c$!
  • Si $(s, c) \notin D$, al ingresar $c$, $M$ se convierte en $M + c$.
• Si $M$ es la cadena vacía, $M$ no se "duplica".

Gumingu, un usuario de ChatChatA, quiere saber el número mínimo de entradas necesarias para ingresar la cadena $T$.

El mensaje actual $M$ comienza como cadena vacía, y cada entrada es una de las siguientes dos acciones:

• Agregar el carácter $c$ a $M$. Según la condición anterior, el mensaje puede "duplicarse".
• Eliminar el último carácter de $M$. Solo se puede elegir esta acción si $M$ no es la cadena vacía.

¡Ayuda a Gumingu a encontrar el número mínimo de entradas necesarias para que el mensaje actual $M$ sea $T$!

Entrada

En la primera línea se da el tamaño $N$ de $D$. ($1 \le N \le 676 = 26^2$)

En la segunda línea se da una cadena $S$ de longitud $N$ compuesta por letras minúsculas del inglés, y en la tercera línea se da una cadena $C$ de longitud $N$ compuesta por letras minúsculas del inglés.

Si denotamos el $i$-ésimo carácter de $S$ como $S_i$ y el $i$-ésimo carácter de $C$ como $C_i$, entonces $D=\{(S_i, C_i) : 1 \le i \le N\}$.

$|D|=N$. Es decir, no se dan pares $(S_i, C_i)$ repetidos.

En la cuarta línea se da una cadena $T$ compuesta por letras minúsculas del inglés que se ingresará. ($1 \le |T| \le 500\,000$)

Salida

En la primera línea, imprime el número mínimo de entradas necesarias para hacer que el mensaje actual sea $T$.

Si no es posible hacer que el mensaje actual sea $T$, imprime $-1$.

Ejemplos

Entrada 1

1
t
a
chatchata

Salida 1

5

Entrada 2

2
ct
ha
chatchata

Salida 2

-1

Entrada 3

2
af
bd
aafaaafaafaaafd

Salida 3

8