Решение задачи Хеширование перемешиванием с Codeforces

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

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

получить пароль p, состоящий из строчных латинских букв, и перемешать буквы в нем, чтобы получить p′ (p′ может остаться равным p);
построить две случайные строки, состоящие из строчных латинских букв, s1 и s2 (любая из них может быть пустой);
полученный хеш h=s1+p′+s2, где сложение — это склеивание строк.
Например, пусть пароль будет p= «abacaba». Тогда p′ может быть равно «aabcaab». Случайные строки s1= «zyx» и s2= «kjh». Тогда h= «zyxaabcaabkjh».

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

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

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