1177. Like Comparisons @ Timus Online Judge

1177. Like Comparisons

Time limit: 1.0 second
Memory limit: 64 MB

Development team of new DBMS asks you to write subroutine for the ‘like’ operator.
‘Like’ operator works as following. It returns true if text string matches specified template. Template is a text string containing any symbols or following special sequences:

%	matches any number of any characters
_	matches any single character
[с1-с2]	matches any single character in the range c1-c2
[c1c2c3…cN]	matches any single character of the set {c1,c2,c3,…,cN}
[^с1-с2]	matches any single character not in the range c1-c2
[^c1c2c3…cN]	matches any single character not in the set {c1,c2,c3,…,cN}

Input

First line contains number of tests N ≤ 1000. Next N lines contain comparisons in the following format:

'string' like 'template'

String or template may contain any symbols with ASCII codes 32-255. Inner entrance of apostrophe symbol (ASCII 39) into string or template is encoded by double apostrophe symbol. Maximal length of string or template is 100 symbols.

Output

For each of N comparisons output single 'YES' or 'NO' at a line.

Sample

input

output

15
'abcde' like 'a'
'abcde' like 'a%'
'abcde' like '%a'
'abcde' like 'b'
'abcde' like 'b%'
'abcde' like '%b'
'25%' like '_5[%]'
'_52' like '[_]5%'
'ab' like 'a[a-cdf]'
'ad' like 'a[a-cdf]'
'ab' like 'a[-acdf]'
'a-' like 'a[-acdf]'
'[]' like '[[]]'
'''''' like '_'''
'U' like '[^a-zA-Z0-9]'

NO
YES
NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO

Problem Author: Pavel Atnashev
Problem Source: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002