Regular expression is an expression which defines a set of strings. In this problem regular expression will contain only small latin letters a-z and special characters ‘?’, ‘*’ и ‘+’. Each letter corresponds to itself in the defined strings. Special character can occur only after some letter and means the number of repetitions of the letter:

For example “ac”, “abc”, “acc”, “abcccc”, and so on match regular expression “ab?c+”.

For the given string find the substring which matches the given regular expression. If there are many such substrings find the most left one. If there are many of those as well fing the longest one.

Input

The first line of input contains number T - the amount of test cases. The description of T test cases follows. The first line of each test case is the given string S of length L. Next line contains number n - the amount of regular expressions. Next n lines describe one regular expression Ri each for which you should find the matching substrings.

Constraints

1 <= T <= 100
1 <= n <= 10
1 <= L <= 200
1 <= R_i <= 100

Output

For each regular expression print the matching substring or -1 if there is no such substring in the given string.

Example

Input:
1
aabbcc
5
b*c
a?b+c+
ab?c
b?c?
a?b?c?

Output:
bbc
abbcc
-1

a