Magnet Transformation

Given two magnets represented by strings a and b, where each magnet is a sequence composed of lowercase letters, uppercase letters, or digits, determine if you can transform magnet a into magnet b using the following operations any number of times on a:

1. Delete a prefix of any positive length. For example, deleting the first 3 characters of 91987 yields 87.
2. Take a suffix (i.e. the last several characters) and move it to the beginning. For example, moving the last 3 characters of 91987 to the front yields 98791.

The transformation is successful if after a sequence of such operations, a becomes exactly equal to b (i.e. they have the same length and identical characters in the same order).

Observation: Since deleting a prefix reduces the length of a and the rotation operation only rearranges characters, the only possibility to achieve equality is to delete exactly |a| - |b| characters from the front (if |b| ≤ |a|). Let s be the remaining string of length |b| (i.e. s = a[|a|-|b|: ]). Then, b must be a rotation of s, which mathematically means:

$$b \text{ is a rotation of } s \iff b \text{ is a substring of } s+s.$$

If |b| > |a|, the transformation is impossible. Otherwise, check whether b is a rotation of s as explained above.

The input includes multiple queries.

inputFormat

The input begins with a single integer T representing the number of test cases. Each test case consists of two lines:

1. The first line contains the string a.
2. The second line contains the string b.

It is guaranteed that the strings consist only of uppercase letters, lowercase letters, or digits.

outputFormat

For each test case, output a single line containing YES if it is possible to transform magnet a into magnet b using the allowed operations, or NO otherwise.

sample

1
ABCD
CDAB

YES