The string ss is given, the string length is odd number. The string consists of lowercase letters of the Latin alphabet.
As long as the string length is greater than 11, the following operation can be performed on it: select any two adjacent letters in the string ss and delete them from the string. For example, from the string "lemma" in one operation, you can get any of the four strings: "mma", "lma", "lea" or "lem" In particular, in one operation, the length of the string reduces by 22.
Formally, let the string ss have the form s=s1s2…sns=s1s2…sn (n>1n>1). During one operation, you choose an arbitrary index ii (1≤i<n1≤i<n) and replace s=s1s2…si−1si+2…sns=s1s2…si−1si+2…sn.
For the given string ss and the letter cc, determine whether it is possible to make such a sequence of operations that in the end the equality s=cs=c will be true? In other words, is there such a sequence of operations that the process will end with a string of length 11, which consists of the letter cc?
The first line of input data contains an integer tt (1≤t≤1031≤t≤103) — the number of input test cases.
The desc
For each test case in a separate line output:
5
abcde
c
abcde
b
x
y
aaaaaaaaaaaaaaa
a
contest
t
YES
NO
NO
YES
YES