Вам задан массив \(s\) содержащий \(n\) различных строк. Каждая строка состоит из \(m\) строчных букв латинского алфавита.
Вам необходимо ответить на \(q\) запросов. Каждый запрос содержит строку \(t\) длины \(m+1\). Посчитайте количество индексов \(i\), таких что, строку \(t\) можно получить из строки \(s_i\), если разрешено вставить одну букву в произвольную позицию.
Выходные данные
Для каждого запроса выведите количество индексов \(i\), таких что, строку из запроса можно получить из строки \(s_i\), если разрешено вставить одну букву в произвольную позицию.
Примечание
Объяснение первого теста из условия:
- строка a может быть превращена в aa вставкой одной буквы;
- и строка a, и строка c может быть превращена в строку ca вставкой одной буквы;
- ни a, ни c не может быть превращена в mm вставкой одной буквы;
- c можно превратить в cf вставкой одной буквы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
a
c
4
aa
ca
mm
cf
|
1
2
0
1
|
|
2
|
6 3
dba
abd
cbb
ada
add
bdd
5
ccbb
abdd
adba
bada
dddd
|
1
3
2
1
0
|