D. Perfect Life
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Dr.Z wants to live a perfect life. In the future, he acquires a time machine that gives him a chance to alter his life. His life is represented by a string $$$S$$$. He can modify the string $$$S$$$ using another string $$$T$$$.

Each modification allows him to choose a positive integer $$$i$$$ in the range $$$[1, |S| - |T| + 1]$$$ and replace the substring $$$S[i : i + |T| - 1]$$$ with $$$T$$$. More precisely, for each $$$j \in [1, |T|]$$$, he sets $$$S_{i+j-1} = T_j$$$. This operation can be performed infinitely many times.Dr.Z considers his life perfect if and only if $$$\forall i \in [1, |S|], S_i = S_{|S| - i + 1}$$$—that is, when the string $$$S$$$ becomes a palindrome.

Dr.Z wants to know whether it's possible for his life to become perfect through these modifications.

There are $$$t$$$ test cases. For each test case, you are given two strings $$$S$$$ and $$$T$$$.If $$$S$$$ can become a palindrome, output Yes. Otherwise, output No.

Input

The first line contains an integer $$$t$$$ means that there are $$$t$$$ test cases.

The next $$$t$$$ lines each contain $$$2$$$ strings $$$S,T\ (1\le |S|\le 10^6,|T|\le 60)$$$.

It is guaranteed that $$$S$$$ and $$$T$$$ contain only uppercase and lowercase letters, and the total length of all strings $$$S$$$ across test cases does not exceed $$$2\times 10^6$$$.

Output

The next $$$t$$$ lines each contain Yes or No.

Example
Input
9
asdppsaAA Aad
pjdaAjcKaA Aad
pjdsdAadaA Aad
pjdjAjcKsA Aad
ABAB AB
BBA AB
abcdDea cd
abcdDea cb
asbAADbbaaa abbc
Output
Yes
Yes
Yes
No
No
Yes
No
Yes
Yes
Note

In the first test case, $$$S$$$ can be turned into a palindrome through 3 modifications. By sequentially choosing $$$i = 1, 4, 2$$$, $$$S$$$ is changed as follows: $$$S \to \text{AadppsaAA}\to \text{AadAadaAA}\to \text{AAadadaAA}$$$.

In the fourth test case,there is no way to change.