Two strings are given - S and T. Your task is to display the number of occurrences of the i-th prefix of the string S in the string T.
Input
The first line contains k - the number of queries (\(k <= length( S)\)), string S< /code> and the string T. Next, k requests are entered, a request for the number of occurrences of the i-th prefix of the string S in the string T.
Output
Output k lines of query responses.
Examples
| # |
Input |
Output |
| 1 |
2 ali balimali
3
0
|
2
8 |