Substring Wildcard Matching

You are given an integer q and then q queries. Each query consists of two strings, s and t. The string t may contain the special character '?' which is treated as a wildcard that can match any single character.

Your task is to determine for each query if t can be found as a contiguous substring of s by checking every possible segment in s of length equal to t. More formally, for each query, you need to check whether there exists an index j (with \(0 \le j \le |s|-|t|\)) such that for all indices \(0 \le k < |t|\), the following holds:

[ s[j+k] = t[k] \quad \text{or} \quad t[k] = \text{'?'} ]

If such an index exists, output YES; otherwise, output NO.

Note: The characters in s and t are lowercase English letters.

inputFormat

The first line contains an integer q representing the number of queries.

For each query, the next two lines contain:

• A string s
• A string t

It is guaranteed that the strings contain only lowercase English letters and, in the case of t, may also contain the character '?'.

outputFormat

For each query, output a single line containing either YES if string t (with wildcards) is a substring of s, or NO otherwise.

## sample

4
abacaba
cab
mississippi
sip
abcdefgh
xyz
applepie
ppi

YES
YES
NO
NO

</p>