You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

塔子哥最近项目写完了，于是他发明了个小游戏约了朋友一起玩。塔子哥写出一个由10个字符组成的字符串，然后他的朋友给出一个用字母、.、*、？ 来组成一个模式字符串。游戏规则如下：

1. .可以匹配任何单个字符。

2. *可以与模式字符串前一个字符组成一组，匹配零个或多个前面的字符

3. ？ 可以与模式字符串前一个字符组成一组，匹配一个或多个前面的字符

当满足以上规则时，朋友获得游戏胜利，输出true，否则为游戏失败，输出false。

已知给出的模式字符串的范围为字母.、*、?。请根据所给的待匹配串和模式字符串，请你设计一个程序判断游戏的输赢。

注意：匹配应该覆盖到整个输入的字符串(而不是局部的)，测试用例中不会出现超出匹配字符范围之外的字符，也不会出现非法的模式字符串。

输入描述

第一行输入匹配次数$m$。

接下来的 $m$ 行每行分别输入待匹配的字符串 $s$ 和模式字符串 $t$ 。

保证输入的待匹配的字符串的长度不超过 $10$。

输出描述

对于每一个测试用例，如果匹配则输出一行true ，如果不匹配则输出 false 。

样例1

输入

3
tt t
tata tata
ttt tt

输出

false
true
false

样例2

输入

5
t t.
t t.*
ta .*
ta .?
t a?

输出

false
true
true
true
false

思考

当$n = 1000$ 如何做？