题目描述

Alice 喜欢读书，并且购买了大量书籍。她把书存放在两个盒子中；每个盒子上都标有一个与盒内所有书籍标题匹配的模式。模式仅由大写/小写英文字母和星号（$*$）组成。星号可以匹配 0 到 4 个字母。例如，标题为 GoneGirl 和 GoneTomorrow 的书可以放入模式为 Gone** 的盒子中，但标题为 TheGoneGirl、Gonetomorrow 和 GoneWithTheWind 的书则不能。

Alice 想知道是否存在一本书可以放入其中任意一个盒子中。也就是说，她想问是否存在一个标题同时与两个盒子的模式匹配。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由两行组成；每行包含一个字符串，其中每个字符要么是大写/小写英文字母，要么是 $*$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 TRUE（如果存在一个字符串同时匹配两个模式）或 FALSE（如果不存在）。

3
****
It
Shakes*e
S*speare
Shakes*e
*peare

Case #1: TRUE
Case #2: TRUE
Case #3: FALSE

提示

在样例 #1 中，标题 It 同时匹配两个模式。注意，星号可以匹配 0 个字符。

在样例 #2 中，标题 Shakespeare 同时匹配两个模式。

在样例 #3 中，不存在同时匹配两个模式的标题。例如，Shakespeare 不行，因为 *peare 模式开头的星号无法匹配 6 个字母。

限制条件

$1 \le T \le 50$。

小数据集（测试集 1 – 可见）

$1 \le$ 每个模式的长度 $\le 200$。

每个模式至多包含 $5$ 个星号。

大数据集（测试集 2 – 隐藏）

$1 \le$ 每个模式的长度 $\le 2000$。

翻译由 DeepSeek V4 Pro 完成