Implement regular expression matching.

In a regular expression:

• a-z matches the corresponding character.
• . matches any single character.
• * matches zero or more of the preceding character.

The entire input string should be matched.

The function would take a string s and the regular expression pattern p.

Examples

s: "a"
p: "a"
match: true

s: "aa"
p: "a"
match: false

s: "ab"
p: "a."
match: true

s: "aa"
p: "a*"
match: true

s: "b"
p: "ba*"
match: true

s: "aabcd"
p: "a*b*c*d*"
match: true

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case the input has two strings s and p.

Expected Output

For each test case, a line containing true or false depending on the match.

Sample Input

6
a a
aa a
ab a.
aa a*
b ba*
aabcd a*b*c*d*

Expected Output

true
false
true
true
true
true

Constraints

• 1 <= T <= 100
• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s contains only lowecase english alphabets.
• p contains '.', '*' and lowecase english alphabets.
• '*' will always be preceded by a valid character.