markdown

E. 删除子序列

每个测试的时间限制：$2$ 秒
每个测试的内存限制：$256$ MB
输入：标准输入
输出：标准输出

题目描述

你有一个字符串 $s$。你可以通过以下操作从 $s$ 中构造一个新的字符串 $t$，最多使用两次该操作：

• 选择任意一个子序列 $s_{i_1}, s_{i_2}, \dots, s_{i_k}$，其中 $1 \le i_1 < i_2 < \dots < i_k \le |s|$；
• 从 $s$ 中删除所选的子序列（$s$ 可能变为空）；
• 将所选的子序列拼接到字符串 $p$ 的右侧（即 $p = p + s_{i_1}s_{i_2}\dots s_{i_k}$）。

当然，初始时字符串 $p$ 是空的。

例如，令 $s = \texttt{ababcd}$。
第一次，选择子序列 $s_1s_4s_5 = \texttt{abc}$，得到 $p = \texttt{abc}$，$s = \texttt{bad}$。
第二次，选择子序列 $s_1s_2 = \texttt{ba}$，得到 $p = \texttt{abcba}$，$s = \texttt{d}$。
因此，我们可以从 $s$ 构造出 $t = \texttt{abcba}$。

请问，能否通过上述算法构造出给定的字符串 $t$？

输入

第一行包含一个整数 $T$（$1 \le T \le 100$）—— 测试用例的数量。

接下来的 $T$ 行每行包含两个测试用例：

• 第一行包含一个由小写拉丁字母组成的字符串 $s$（$1 \le |s| \le 400$）—— 初始字符串。
• 第二行包含一个由小写拉丁字母组成的字符串 $t$（$1 \le |t| \le |s|$）—— 你想要构造的字符串。

保证所有测试用例中 $s$ 的总长度不超过 $400$。

输出

输出 $T$ 个答案 —— 每个测试用例一行。
如果能够构造出 $t$，则输出 YES（不区分大小写），否则输出 NO（不区分大小写）。

示例

输入

4
ababcd
abcba
a
b
defi
fed
xyz
x

输出

YES
NO
NO
YES