ICPC12C - The Encrypted Password

Encrypting passwords is one of the most important problems nowadays, and you trust only the encryption algorithms which you invented, and you have just made a new encryption algorithm.

Given a password which consists of only lower case English letters, your algorithm encrypts this password using the following 3 steps (in this given order):

  1. Swap two different characters of the given password (you can do this step zero or more times).
  2. Append zero or more lower case English letters at the beginning of the output of step one.
  3. Append zero or more lower case English letters to the end of the output of step two.

And the encrypted password is the output of step three.

You have just finished implementing the above algorithm and applied it on many passwords. Now you want to make sure that there are no bugs in your implementation, so you decided to write another program which validates the output of the encryption program. Given the encrypted password and the original password, your job is to check whether the encrypted password may be the result of applying your algorithm on the original password or not.

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integerĀ T, the number of test casesĀ (1 <= T <= 100). Followed by the test cases, each test case is on two lines. The first line of each test case contains the encrypted password. The second line of each test case contains the original password. Both the encrypted password and the original password are at least 1 and at most 100,000 lower case English letters (from 'a' to 'z'), and the length of the original password is less than or equal the length of the encrypted password.

Output

For each test case, print on a single line one word, 'YES' (without the quotes) if applying the algorithm on the original password may generate the encrypted password, otherwise print 'NO' (without the quotes).

Example

Input:
3
abcdef
ecd
cde
ecd
abcdef
fcd

Output:
YES
YES
NO

Added by:Kawmia Institutes
Date:2013-01-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ACPC 2012

hide comments
2015-06-09 05:07:07 :.Mohib.:
Finally done :) awsm que...!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.