Problem Description

  Sometimes we need to check that if a given string matches a format string or not. Look at the format string: (a)*(b)+(c)?(f|d), * represents the substring in the brackets before appears any times, if the format string is (ab)* ,then string “ababab” or null string match the format string .And + represents the substring in the brackets appears one or more times, for the format (ab)+ , the null string can’t match the format string. And the ? represents the substring in the brackets before appears none or once , and when you get the symbol |, either the substring s1(left of the symbol | ) appear once, or the substring s2(right of the symbol) appear once, but they don’t appear together. For example, (f|h) represent that either ‘f’ or ‘h’ appears for once.

Input

  In the first line, there is N represents the case number. Then N lines follow, in each line, there is a string. The length of each string won’t exceed 100000, and 1<=N<=1000. The letters appear in the string are only lower letters.

Output

  The format string is given before and won’t be changed. The format string is (a)*aba((b)?(d)+)?h((f)|(k))+
  For each case, just print “YES” if the input string mathes the format string, or “NO”.

4
abahf
aababdddhffkk
babbbdh
aaaaaaaaabahffffffff

YES
YES
NO
YES

Author

wangye