Given a text 'str' and a wildcard pattern 'pattern', your task is to complete the function wildcard that returns '1' if the wildcard pattern is matched with text else returns '0'.

 your task is to complete the function wildcard that returns '1' if the wildcard pattern is matched with text else returns '0'.

Given a text 'str' and a wildcard pattern 'pattern', your task is to complete the function wildcard that returns '1' if the wildcard pattern is matched with text else returns '0'.The function takes two strings as arguments 'pattern' and 'str'.

The wildcard pattern can include the characters ‘?’ and ‘*’
‘?’ – matches any single character
‘*’ – Matches any sequence of characters (including the empty sequence)

For example,

Text = "baaabab",
Pattern = “*****ba*****ab", output : true
Pattern = "baaa?ab", output : true
Pattern = "ba*a?", output : true
Pattern = "a*ab", output : false 

Example

Input

2

a*a

aa

a?a

aa

Output

1

0

// { Driver Code Starts
#include<bits/stdc++.h>

using namespace std;
int wildCard(string pattern, string str);
int main() {
    int t;
    cin >> t;
    while (t--) {
        string pat, text;
        cin >> pat;
        cin.ignore(numeric_limits < streamsize > ::max(), '\n');
        cin >> text;
        cout << wildCard(pat, text) << endl;
    }
}
// } Driver Code Ends


/*You are required to complete this method*/
int wildCard(string pattern, string str) {
    int m = pattern.size(), n = str.size();

    int a[n + 1][m + 1];
    memset(a, 0, sizeof(a));
    a[0][0] = 1;

    for (int i = 1; i <= m; i++) {
        if (pattern[i - 1] == '*')
            a[0][i] = a[0][i - 1];
        else
            a[0][i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {

   if ((pattern[j - 1] == str[i - 1]) || (pattern[j - 1] == '?'))
                a[i][j] = a[i - 1][j - 1];
            else if (pattern[j - 1] == '*')
                a[i][j] = a[i - 1][j] || a[i][j - 1];
            else
                a[i][j] = 0;
        }

    }
    return a[n][m];

}