题目描述

Alice likes reading and buys a lot of books. She stores her books in two boxes; each box is labeled with a pattern that matches the titles of all of the books stored in that box. A pattern consists of only uppercase/lowercase English alphabet letters and stars ($*$). A star can match between zero and four letters. For example, books with the titles GoneGirl and GoneTomorrow can be put in a box with the pattern Gone**, but books with the titles TheGoneGirl, Gonetomorrow, and GoneWithTheWind cannot.

Alice is wondering whether there is any book that could be stored in either of the boxes. That is, she wonders if there is a title that matches both boxes' patterns.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each consists of two lines; each line has one string in which each character is either an uppercase/lowercase English letter or $*$.

输出格式

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from 1) and $y$ is TRUE if there is a string that matches both patterns, or FALSE if not.

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

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

提示

In sample case #1, the title It matches both patterns. Note that it is possible for a * to match zero characters.

In sample case #2, the title Shakespeare matches both patterns.

In sample case #3, there is no title that matches both patterns. Shakespeare, for example, does not work because the * at the start of the *peare pattern cannot match six letters.

Limits

$1 \le T \le 50$.

Memory limit: $1\text{GB}$.

Small dataset (Test set 1 - Visible)

$1 \le$ the length of each pattern $\le 200$.

Each pattern contains at most $5$ stars.

Large dataset (Test set 2 - Hidden)

$1 \le$ the length of each pattern $\le 2000$.