# Wildcard Matching

1000ms    65536K
2    0
Difficult

Description

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Input

There are mulitple test cases.

The first line contain a positive integer N. means there are N test cases.

Following N lines, for each line contains two strings sperated by space. the first one is the text string, the second is the pattern string.

Output

For each line output true if the test case is match, false if not match.

Sample Input

7
aa a
aa aa
aaa aa
aa *
aa a*
ab ?*
aab c*a*b

Sample Output

false
true
false
true
true
true
false

Source

Editor

keefo on 2015-01-23 04:27:36