A. Хеширование перемешиванием
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп недавно создал новый веб сервис. Как в любом современном сервисе, в нем есть возможность авторизации. А это автоматически подразумевает угрозы безопасности.

Поликарп решил сохранять хеш пароля, полученный по следующему алгоритму:

  1. получить пароль $$$p$$$, состоящий из строчных латинских букв, и перемешать буквы в нем, чтобы получить $$$p'$$$ ($$$p'$$$ может остаться равным $$$p$$$);
  2. построить две случайные строки, состоящие из строчных латинских букв, $$$s_1$$$ и $$$s_2$$$ (любая из них может быть пустой);
  3. полученный хеш $$$h = s_1 + p' + s_2$$$, где сложение — это склеивание строк.

Например, пусть пароль будет $$$p =$$$ «abacaba». Тогда $$$p'$$$ может быть равно «aabcaab». Случайные строки $$$s1 =$$$ «zyx» и $$$s2 =$$$ «kjh». Тогда $$$h =$$$ «zyxaabcaabkjh».

Обратите внимание, что нельзя удалять или добавлять буквы в $$$p$$$, чтобы получить $$$p'$$$, можно только менять их порядок.

Теперь Поликарп просит вас помочь ему в реализации модуля проверки пароля. По данному паролю $$$p$$$ и хешу $$$h$$$, проверьте, что $$$h$$$ может являться хешом пароля $$$p$$$.

Вам нужно ответить на $$$t$$$ наборов входных данных.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных содержится непустая строка $$$p$$$, состоящая из строчных латинских букв. Длина $$$p$$$ не превышает $$$100$$$.

В второй строке каждого набора входных данных содержится непустая строка $$$h$$$, состоящая из строчных латинских букв. Длина $$$h$$$ не превышает $$$100$$$.

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

На каждый набор входных данных выведите «YES», если данный хеш $$$h$$$ может быть получен по данному паролю $$$p$$$, и «NO» в противном случае.

Пример
Входные данные
5
abacaba
zyxaabcaabkjh
onetwothree
threetwoone
one
zzonneyy
one
none
twenty
ten
Выходные данные
YES
YES
NO
YES
NO
Примечание

Первый набор входных данных объяснен в условии.

Во втором наборе входных данных и $$$s_1$$$, и $$$s_2$$$ пусты, а $$$p'=$$$ «threetwoone» — это перемешанная $$$p$$$.

В третьем наборе входных данных хеш нельзя получить из пароля.

В четвертом наборе входных данных $$$s_1=$$$ «n», $$$s_2$$$ пуста, а $$$p'=$$$ «one» — это перемешанная $$$p$$$ (даже несмотря на то, что они совпадают).

В пятом наборе входных данных хеш нельзя получить из пароля.