String matching is an important problem where we want to find whether a string (or sometimes called pattern) can be found within a larger string. In other words, whether a pattern P exists as a substring of string S. Naively, we can solve this problem by iterating through all possible substrings of S in O(S^{2}) time, but usually the length of S and P are quite large such that a quadratic timecomplexity solution like this is not fast enough. This problem has been studied extensively (e.g., in computational biology) and many algorithms have been proposed to solve this problem. You may have heard (or better, familiar with) some of these wellknown algorithms: KnuthMorrisPrat (KMP) algorithm, RabinKarp algorithm, and AhoCorasick algorithm. These algorithms can solve the string matching problem in linear timecomplexity.
Red is the founder of a new startup game developer company. When Red developed his first game with his team, Red found the exact problem which he has learnt back in his undergraduate study, the string matching problem. However, being an ignorant person, Red did not pay much attention on this subject and managed to barely pass the exam. Red delegated this problem to one of his new programmer which also is a freshgraduate, with the hope that this new guy still remember the linear timecomplexity solution for this problem.
Unfortunately, instead of implementing a (correct) string matching algorithm, this new guy implemented a wrong one:
Knowing that his solution is linear timecomplexity, this new guy is confident that this solution works. However, of course you, being a competitive programmer, realize that this solution is simply wrong.
For example, let P = "ABABC" and S = "ABABABCABA".
First round:
S: ABABABCABA P: ABABC
P is not a prefix of S and P_{4} ≠ S_{4} (x = 4 in 0based index), so update S as suffix of S starting from index 4 + 1 (= 5): ABABABCABA → BCABA.
Second round:
S: BCABA P: ABABC
P is not a prefix of S and P_{0} ≠ S_{0} (x = 0 in 0based index), so update S as suffix of S starting from index 0 + 1 (= 1): BCABA → CABA.
Third round:
S: CABA P: ABABC
S is lower than P (4 < 5), so output "NO" and terminate.
Therefore, this algorithm will produce "NO" output for P = ABABC and S = ABABABCABA, even though we can find P in S: AB(ABABC)ABA.
You want to analyze the damages caused by this algorithm, so, as the first step, you should reproduce this algorithm. Given a pattern P and a string S, output whether P exists in S according to the aforementioned algorithm.
The first line of input contains an integer T (T ≤ 100) denoting the number of cases. Each case contains two string P and S separated by a single space denoting the pattern and the string, respectively. P and S consist of uppercase alphabetic characters only (AZ) and have length between 1 and 20,000 characters.
For each case, output in a line "Case #X: Y" where X is the case number, starts from 1, and Y is the output of the algorithm described in the problem statement (YES or NO).
