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.

No tag edit access

E. Erase Subsequences

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a string $$$s$$$. You can build new string $$$p$$$ from $$$s$$$ using the following operation no more than two times:

- choose any subsequence $$$s_{i_1}, s_{i_2}, \dots, s_{i_k}$$$ where $$$1 \le i_1 < i_2 < \dots < i_k \le |s|$$$;
- erase the chosen subsequence from $$$s$$$ ($$$s$$$ can become empty);
- concatenate chosen subsequence to the right of the string $$$p$$$ (in other words, $$$p = p + s_{i_1}s_{i_2}\dots s_{i_k}$$$).

Of course, initially the string $$$p$$$ is empty.

For example, let $$$s = \text{ababcd}$$$. At first, let's choose subsequence $$$s_1 s_4 s_5 = \text{abc}$$$ — we will get $$$s = \text{bad}$$$ and $$$p = \text{abc}$$$. At second, let's choose $$$s_1 s_2 = \text{ba}$$$ — we will get $$$s = \text{d}$$$ and $$$p = \text{abcba}$$$. So we can build $$$\text{abcba}$$$ from $$$\text{ababcd}$$$.

Can you build a given string $$$t$$$ using the algorithm above?

Input

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

Next $$$2T$$$ lines contain test cases — two per test case. The first line contains string $$$s$$$ consisting of lowercase Latin letters ($$$1 \le |s| \le 400$$$) — the initial string.

The second line contains string $$$t$$$ consisting of lowercase Latin letters ($$$1 \le |t| \le |s|$$$) — the string you'd like to build.

It's guaranteed that the total length of strings $$$s$$$ doesn't exceed $$$400$$$.

Output

Print $$$T$$$ answers — one per test case. Print YES (case insensitive) if it's possible to build $$$t$$$ and NO (case insensitive) otherwise.

Example

Input

4 ababcd abcba a b defi fed xyz x

Output

YES NO NO YES

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/29/2020 04:25:21 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|