#SUBSN. Subsequence

Subsequence

 

A subsequence is a sequence that can be derived from another sequence by deleting some
elements without changing the order of the remaining elements. For example “abd” is a
subsequence of “abcdef”. - Wikipedia
Your task in this problem is to decide if a given string is a subsequence of another string or not?
Easy?

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example “abd” is a subsequence of “abcdef”. - Wikipedia.

Your task in this problem is to decide if a given string is a subsequence of another string or not?

Easy?

Input

The first line of input will be the number of test cases. Each test case will start with a line contains a string S, S will have letters from 'a' to 'z' and the length of S <= 100,000. This line will be followed by a number Q which is the number of queries you have to answer for the given string S, 1 <= Q <= 1000. Each of the next Q lines will contain a string T, T will have letter from 'a' to 'z' and the length of T <= 200. For each T you have to decide if T is a subsequence of S or not.

Output

For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1. The next Q lines will have either “YES” or “NO” if the cross-ponding T is a subsequence of S or not respectively.

Example

Input:
1
abcdef
3
abd
adb
af

Output: Case 1: YES NO YES

</p>

Editors note:
Strings in the input can be empty. Read data carefully to avoid issues. There should be no extra withespaces, of course except '\n'.