Transformable Palindrome

Given a string S consisting of lowercase letters along with two special characters: '?' and '*'. The character '?' can be replaced with any single letter, while '*' can be replaced with any sequence of letters (including an empty string). The task is to determine whether it is possible to transform S into a palindrome by choosing appropriate substitutions for the wildcard characters.

A string S of length n is a palindrome if it satisfies $$ \forall \; 0 \leq i < n, \quad S[i] = S[n-1-i]. $$

For example:

• a?c?a can be transformed into a palindrome (e.g. "acoca") so the answer is YES.
• abcdef cannot be transformed into a palindrome so the answer is NO.

It is guaranteed that the string S only consists of lowercase English letters and the special characters '?' and '*'.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
S1
S2
...
ST

Here, T is a positive integer representing the number of test cases. Each of the following T lines contains a single string S.

outputFormat

For each test case, output a single line containing YES if the string can be transformed into a palindrome by replacing '?' with any letter and '*' with any sequence of letters; otherwise, output NO.

## sample

5
a?c?a
ab*ba
aa?*?aa
abcdef
ab?cd

YES
YES
YES
NO
NO

</p>