Description

In computer (software) technology, a wildcard character can be used to substitute for any other character or characters in a string.

In this problem, only two kinds of wildcard characters are considered:

'*' : matches any zero or more letters. and

'?' : matches exactly one letter

Given a list of patterns(which may consist of wildcards) and words, you are to find whether the pattern can match the word.(matches are not case sensitive)

Input

The first line of the input contains an integer N (N<=100) indicating the number of case. Then from the second line, there are 2*N lines,for each line(start at 2),the even one consist a pattern, the odd one consist a word(to be matched by previous line's pattern), you are to find whether the pattern can match the word(at next line of the pattern). The patterns only consisting of letters and wildcards. Each pattern also occupies a single line.

All words and patterns's length less than 200.

Output

For each pattern and word, if the pattern can match the word, output "Matched!!!"， else output "Failed...".

Sample

Input

1
ab*??ab*ab
abababababab

Output

Matched!!!

Hint

串长200以内

Source: LCS