Description

你有一个字符串 s 和一个芯片，你可以将芯片放在该字符串的任意字符上。

放置芯片后，你可以将芯片向右移动若干次（也可以不移动），即你可以多次执行如下操作：如果芯片当前在第 i 个位置，你可以将其移动到第 i+1 个位置。当然，如果芯片已经在最后一个位置，则无法再向右移动。

在向右移动结束后，你可以将芯片向左移动若干次（也可以不移动），即你可以多次执行如下操作：如果芯片当前在第 i 个位置，你可以将其移动到第 i−1 个位置。当然，如果芯片已经在第一个位置，则无法再向左移动。

每当你放置芯片或移动芯片时，你都要记录下芯片当前所在位置的字符。例如，如果 s 为 abcdef，你将芯片放在第 3 个字符上，向右移动 2 次，再向左移动 3 次，你记录下的字符串为 cdedcb。

现在给定两个字符串 s 和 t，你的任务是判断，是否存在一种上述操作方式，使得最终记录下的字符串恰好为 t。

Format

Input

第一行包含一个整数 q（1≤q≤500），表示测试用例的数量。

每个测试用例包含两行。第一行是字符串 s（1≤∣s∣≤500），第二行是字符串 t（1≤∣t∣≤2∣s∣−1）。两个字符串均由小写英文字母组成。

保证所有测试用例中 ∣s∣ 的总和不超过 500。

Output

对于每个测试用例，如果可以通过上述过程从 s 得到 t，输出 "YES"；否则输出 "NO"。

你可以用任意大小写输出答案（YES、yes、Yes 都可以被识别为正解，NO、no、nO 都可以被识别为负解）。

Samples

6
abcdef
cdedcb
aaa
aaaaa
aab
baaa
ab
b
abcdef
abcdef
ba
baa

YES
YES
NO
YES
YES
NO

Limitation

1s, 1024KiB for each test case.