Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.
Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.
Выходные данные
Вывести k строк с ответами на запросы.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 ali balimali
3
0
|
2
8 |