Shriha likes to play with strings. She has come up with a new task given by her teacher Amit. Amit will give a string C, made of lowercase Latin letters to Shriha and a special type of string which he calls twist_of_fate string V, containing lowercase latin letters and asterisks symbol i.e. '*'.
Both the strings C and V have their index starting from 1.
Shriha can generate different strings R from the twist_of_fate string V by following the rule of generation which says- twist_of_fate string V is said to generate a string R if and only if R can be obtained from V by replacing all the asterisks with arbitrary (possibly empty) lowercase Latin letter strings.
Considering the ith symbol of the string C, Shriha has to calculate the smallest index bi ≥ i such that the substring Ci...Cbi contains at least one of the strings generated by twist_of_fate string V. In case Shriha is unable to find any such index i.e if any such index bi doesn't exist, then bi = -1.
Shriha's goal is to calculate all the values b1, b2, ... , b|C|. Since she is just 13 years old and unable to complete this task on her own, she has asked you to help her with this task.
where |C| = length of string C
Note:- The twist_of_fate string V always has a '*' at it's index 1 i.e. string V always starts with asterisk '*'.
Input :
The first line of input contains an integer T denoting the number of test cases and the description of T test cases are as follows:-
The first line of each test case contains a twist_of_fate string V
and the second line of the test case contains a lowercase Latin string C.
Output :
For each test case, output a single line containing |C| space-separated integers, denoting b1 ,b2 , ..., b|C|.
Constraints :
1 ≤ T ≤ 102
1 ≤ |C| , |V| ≤ 103
Maximum number of asterisks possible in string V of any test case is 500
Problem Setter: MAHIMA SINGH
Explanation:
Test case 1:-
Showing that for every index i the value of bi is correct:
- b1 = 1. The corresponding substring a contains the string a. String a can be generated by replacing both asterisks with empty strings.
- b2 = 3. The corresponding substring ba contains the string ba. The string ba can be obtained if we replace the first asterisk with b and the second one with an empty string.
- b3 = 3. The corresponding substring a contains the string a.
- b4 = 5. The corresponding substring ca contains the string ca. The string ca can be obtained if we replace the first asterisk with c and the second one with an empty string.
- b5 = 5. The corresponding substring a contains the string a.
- b6 = 7. The corresponding substring ba contains the string ba. The string ba can be obtained if we replace the first asterisk with b and the second one with an empty string.
- b7 = 7. The corresponding substring a contains the string a.
Test case 2:-
Now checking again for every index i:
- b1 = 2. The corresponding substring ab contains ab. The string ab can be obtained if we replace all the asterisks with empty strings.
- b2 = 6. The corresponding substring bacab contains bacab. The string bacab can be obtained if we replace the first asterisk with b, the second one with the string ca and the third one with an empty string.
- b3 = 6. The corresponding substring acab contains ab.
- b4 = 6. The corresponding substring cab contains cab. The string cab can be obtained if you replace the first asterisk with c, and the rest with empty strings.
- b5 = 6. The corresponding substring ab contains ab.
- b6 = b7 = -1. Neither ba nor a doesn't contain any substring, generated by *a*b*.
