Problem Description

You work as a programmer at a certain company.

At this company, you are responsible for determining whether a specified substring is contained within a certain contiguous part of a string collected from users.

For example, the string rhd is contained within the string thisisrhdcontest, but it is not contained within the strings thanks or ratheads.

However, due to inquiries from users, it has been discovered that unwanted characters, as noise, have been included in the strings submitted by users, preventing the desired determination from being made.

Therefore, you have been tasked with creating a program to process the following $ Q $ queries from $ 1 $ to $ Q $.

Query $ i $: "Given strings $ S_i $ and $ T_i $. Select some characters $ x_1 $, $ x_2 $, ..., $ x_k $ (it is also acceptable to select no characters), and remove all selected characters from string $ S_i $ to obtain a string $ S'_i $. Determine if string $ T_i $ can be contained within any of the possible strings $ S'_i $."

For example, when $ S_1 $ = ratheads, $ T_1 $ = rhd, if we remove the characters a, e, t from $ S_1 $, we get the string $ S'_1 $ = rhds, which contains the string $ T_1 $ = rhd. Therefore, it can be said that the string $ T_1 $ can be contained.

Input Format

The input is given from the standard input in the following format:

$ Q $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ : $ S_Q $ $ T_Q $

• The first line contains the number of queries $Q\ (1\ ≦\ Q\ ≦\ 5,000)$.
• The next $ Q $ lines contain the information related to the queries. The $i\ (1\ ≦\ i\ ≦\ Q)$th line contains two strings $ S_i $, $T_i\ (1\ ≦\ ｜S_i｜\ ≦\ 50,\ 1\ ≦\ ｜T_i｜\ ≦\ 50)$ consisting of lowercase English letters, separated by a space.

Output Format

Output $ Q $ lines. The $i\ (1\ ≦\ i\ ≦\ Q)$th line should contain the answer for query $ i $. If string $ T_i $ can be contained in query $ i $, output YES; otherwise, output NO. Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
ratheads rhd
thisisrhdcontest rhd
yes no
abba aba

Sample Output #1

YES
YES
NO
NO

Sample Input #2

5
abcdef bdf
aabbccdd b
abcabcabc aaba
abcdcba dba
ababababa aba

Sample Output #2

YES
YES
NO
YES
YES

Notes/Hints

Sample Explanation 1

There are $ 4 $ queries:
- Query $ 1 $ is shown in the example in the problem statement. By removing the characters a, e, t from $ S_1 $, we get the string $ S'_1 $ = rhds, which contains the string $ T_1 $, so we output YES.
- In query $ 2 $, the string $ T_2 $ is contained in string $ S_2 $ without removing any characters, so we output YES.
- In query $ 3 $, no matter how we remove characters from string $ S_3 $, the string $ T_3 $ cannot be contained in any possible string $ S'_3 $, so we output NO.
- In query $ 4 $, no matter how we remove characters from string $ S_4 $, the string $ T_4 $ cannot be contained in any possible string $ S'_4 $, so we output NO.

Note that when specifying characters to remove, you cannot leave any of the specified characters partially removed.

见题面 Input 部分

见题面 Output 部分