В Моржландии выпускается газета с названием s1, состоящем из строчных букв латинского алфавита. Маленький морж Клычок хочет купить несколько таких газет, вырезать из них названия, склеить их друг за другом и стереть некоторые буквы так, чтобы получилось слово s2. Считается, что когда Клычок стирает какую-то букву, на ее месте не образуется пустое место. То есть строка остается неразрывной и по-прежнему состоит только из маленьких букв латинского алфавита.
Например, заголовок газеты — «abc». Взяв два таких заголовка и склеив, получится «abcabc». Если стереть буквы на позициях 1 и 5 получится слово «bcac».
Какое наименьшее количество газетных заголовков s1 понадобится Клычку, чтобы он мог их склеить, стереть несколько букв и получить слово s2?
Выходные данные
Если получить слово s2 описанным выше способом невозможно, выведите «-1» (без кавычек). Иначе выведите наименьшее количество газетных заголовков s1, которое понадобится, чтобы получить слово s2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abc
xyz
|
-1
|
|
2
|
abcd
dabc
|
2
|