Вам заданы две строки \(s\) и \(t\), состоящие из строчных букв латинского алфавита. Также у вас есть строка \(z\), которая изначально пуста. Вы хотите, чтобы строка \(z\) стала равна строке \(t\). Для этого вы можете выполнять следующую операцию: добавить любую подпоследовательность строки \(s\) в конец строки \(z\). Подпоследовательность — это последовательность, которая получается из данной путем удаления нуля или более ее элементов. Например, если \(z = ac\), \(s = abcde\), вы можете превратить \(z\) в следующие строки за одну операцию:
- \(z = acace\) (если выберете подпоследовательность \(ace\));
- \(z = acbcd\) (если выберете подпоследовательность \(bcd\));
- \(z = acbce\) (если выберете подпоследовательность \(bce\)).
Обратите внимание, что строка \(s\) не меняется после операций.
Посчитайте минимальное количество операций, необходимое для того, чтобы превратить строку \(z\) в строку \(t\).
Выходные данные
На каждый набор входных данных выведите одно число — минимальное количество операций, необходимое для того, чтобы превратить строку \(z\) в строку \(t\). Если это невозможно выведите \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
aabce
ace
abacaba
aax
ty
yyt
|
1
-1
3
|