Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

implementation

strings

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Shuffle Hashing

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp has built his own web service. Being a modern web service it includes login feature. And that always implies password security problems.

Polycarp decided to store the hash of the password, generated by the following algorithm:

- take the password $$$p$$$, consisting of lowercase Latin letters, and shuffle the letters randomly in it to obtain $$$p'$$$ ($$$p'$$$ can still be equal to $$$p$$$);
- generate two random strings, consisting of lowercase Latin letters, $$$s_1$$$ and $$$s_2$$$ (any of these strings can be empty);
- the resulting hash $$$h = s_1 + p' + s_2$$$, where addition is string concatenation.

For example, let the password $$$p =$$$ "abacaba". Then $$$p'$$$ can be equal to "aabcaab". Random strings $$$s1 =$$$ "zyx" and $$$s2 =$$$ "kjh". Then $$$h =$$$ "zyxaabcaabkjh".

Note that no letters could be deleted or added to $$$p$$$ to obtain $$$p'$$$, only the order could be changed.

Now Polycarp asks you to help him to implement the password check module. Given the password $$$p$$$ and the hash $$$h$$$, check that $$$h$$$ can be the hash for the password $$$p$$$.

Your program should answer $$$t$$$ independent test cases.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a non-empty string $$$p$$$, consisting of lowercase Latin letters. The length of $$$p$$$ does not exceed $$$100$$$.

The second line of each test case contains a non-empty string $$$h$$$, consisting of lowercase Latin letters. The length of $$$h$$$ does not exceed $$$100$$$.

Output

For each test case print the answer to it — "YES" if the given hash $$$h$$$ could be obtained from the given password $$$p$$$ or "NO" otherwise.

Example

Input

5 abacaba zyxaabcaabkjh onetwothree threetwoone one zzonneyy one none twenty ten

Output

YES YES NO YES NO

Note

The first test case is explained in the statement.

In the second test case both $$$s_1$$$ and $$$s_2$$$ are empty and $$$p'=$$$ "threetwoone" is $$$p$$$ shuffled.

In the third test case the hash could not be obtained from the password.

In the fourth test case $$$s_1=$$$ "n", $$$s_2$$$ is empty and $$$p'=$$$ "one" is $$$p$$$ shuffled (even thought it stayed the same).

In the fifth test case the hash could not be obtained from the password.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 19:32:53 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|