F. DDDDC
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

While preparing a problem for the $$$3\text{D}(\text{C}^{4})$$$ contest, Emanuel became interested in abbreviations. Some seem intuitive to him, while others do not. He has asked you to write a program to tell them apart.

A string $$$t$$$ is an intuitive abbreviation of a string $$$s$$$ if $$$t$$$ can be obtained by deleting zero or more characters from $$$s$$$ without changing the order of the remaining characters. Each occurrence of a letter in $$$t$$$ must correspond to a distinct occurrence in $$$s$$$.

For example, DDDDC is an intuitive abbreviation of DIRTYDEEDSDONEDIRTCHEAP, and DCC is an intuitive abbreviation of DINOSSAUROCODECUP.

For each test case, determine whether the second string is an intuitive abbreviation of the first.

Input

The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^{5}$$$), the number of test cases.

Each test case consists of one line containing two space-separated strings $$$s$$$ and $$$t$$$ ($$$1 \leq |s|,|t| \leq 10^{5}$$$). Both strings consist only of uppercase English letters.

The sum of the lengths of all strings $$$s$$$ and $$$t$$$ does not exceed $$$10^{6}$$$.

Output

For each test case, print SIM (Portuguese for "yes") if $$$t$$$ is an intuitive abbreviation of $$$s$$$, or NAO ("no") otherwise.

Example
Input
8
DCCCODECUP DCCCC
DCCCODECUP DDDDC
DIRTYDEEDSDONEDIRTCHEAP DDDDC
MVKAIO MK
HIGINOH HGH
DCCCCC DCCCC
ESTADOSUNIDOS EEUU
TREINAMENTOPARAAMARATONA TREM
Output
SIM
NAO
SIM
SIM
SIM
SIM
NAO
SIM