题目描述

$\texttt{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.$\texttt{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.

$\texttt{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 $\texttt{Yes}$. Otherwise, output $\texttt{No}$.

输入格式

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$.

输出格式

The next $t$ lines each contain $\texttt{Yes}$ or $\texttt{No}$.

9
asdppsaAA Aad
pjdaAjcKaA Aad
pjdsdAadaA Aad
pjdjAjcKsA Aad
ABAB AB
BBA AB
abcdDea cd
abcdDea cb
asbAADbbaaa abbc

Yes
Yes
Yes
No
No
Yes
No
Yes
Yes

提示

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.