You are writing a simple text editor, and one of the features you need to implement is a text search. Given a pattern, the search mechanism should return the position of its first occurrence, starting from the current position, or indicate that the pattern cannot be found. Searches are case sensitive, and do not wrap. The search dialog contains a text box and a checkbox labeled "Whole Word". When the "Whole Word" option is selected, the matched sequence must either be preceded by a space to its left or be at the very beginning of the text. Similarly, it must also either be followed by a space to its right or be at the very end of the text.

You are given a String text consisting of letters and spaces. You are also given a String search, a sequence of letters representing the search pattern, and a String wholeWord, which is either "Y" or "N", indicating whether or not the "Whole Word" option is checked. An int start represents the current position in the text from where you start searching. Find the index of the first match, or -1 if there is none. The index of the match here means the index of its first character. Both the starting index and the return index are zero based.

Input

Input starts with T <= 100 - the number of testcases. Following T testcases, each contains text, search, WholeWord, and start in 4 separate lines. See sample input for clarifications. Note that there is always a blank line in start of every of testcase.

Size of text string >= 1 and <= 50 and will contain only 'a'-'z', 'A'-'Z' and spaces. Size of search string >= 1 and <= 50 and will contain only 'a'-'z', 'A'-'Z'. WholeWord string will be either "Y" or "N". Start will be from 0 to N-1 where N is the size of text.

Output

For each testcase, if search string is found in text string depending upon the WholeWord string and start index as mentioned above, output the index (0-based) of the first character where the string is found, else output "-1" in a single line.

Example

Input:
3

We dont need no education
ed
N
13

We dont need no thought control
We
Y
0

No dark sarcasm in the classroom
The
Y
5

Output:
16
0
-1