该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

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

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

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

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

Format

Input

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

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

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

输出格式

对于每个测试用例，如果可以通过上述过程从 s 得到 t，输出 "YES"；否则输出 "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. 第一个测试用例在题目描述中已经给出。

第二个测试用例，你可以将芯片放在第 1 个位置，向右移动两次，再向左移动两次。

第四个测试用例，你可以将芯片放在第 2 个位置，然后不移动。

第五个测试用例，你可以将芯片放在第 1 个位置，向右移动 5 次，然后结束操作。