C. Получи строку
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы две строки $$$s$$$ и $$$t$$$, состоящие из строчных букв латинского алфавита. Также у вас есть строка $$$z$$$, которая изначально пуста. Вы хотите, чтобы строка $$$z$$$ стала равна строке $$$t$$$. Для этого вы можете выполнять следующую операцию: добавить любую подпоследовательность строки $$$s$$$ в конец строки $$$z$$$. Подпоследовательность — это последовательность, которая получается из данной путем удаления нуля или более ее элементов. Например, если $$$z = ac$$$, $$$s = abcde$$$, вы можете превратить $$$z$$$ в следующие строки за одну операцию:

  1. $$$z = acace$$$ (если выберете подпоследовательность $$$ace$$$);
  2. $$$z = acbcd$$$ (если выберете подпоследовательность $$$bcd$$$);
  3. $$$z = acbce$$$ (если выберете подпоследовательность $$$bce$$$).

Обратите внимание, что строка $$$s$$$ не меняется после операций.

Посчитайте минимальное количество операций, необходимое для того, чтобы превратить строку $$$z$$$ в строку $$$t$$$.

Входные данные

Первая строка содержит единственное число $$$T$$$ ($$$1 \le T \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит строку $$$s$$$ ($$$1 \le |s| \le 10^5$$$), состоящую из строчных букв латинского алфавита.

Вторая строка каждого набора входных данных содержит строку $$$t$$$ ($$$1 \le |t| \le 10^5$$$), состоящую из строчных букв латинского алфавита.

Гарантируется, что суммарная длина строк $$$s$$$ и $$$t$$$ во входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно число — минимальное количество операций, необходимое для того, чтобы превратить строку $$$z$$$ в строку $$$t$$$. Если это невозможно выведите $$$-1$$$.

Пример
Входные данные
3
aabce
ace
abacaba
aax
ty
yyt
Выходные данные
1
-1
3