B. Общажные войны
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хоссам решил проникнуть в комнату Хемоса, пока он спит, и сменить пароль на его ноутбуке. Он уже знает исходный пароль, равный строке $$$s$$$ длины $$$n$$$. Он также знает, что существуют $$$k$$$ особых букв в алфавите: $$$c_1,c_2,\ldots, c_k$$$.

Хоссам написал программу, которая делает следующее.

  1. Программа рассматривает текущий пароль $$$s$$$ некоторой длины $$$m$$$.
  2. Затем она находит все такие позиции $$$i$$$ ($$$1\le i<m$$$), что $$$s_{i+1}$$$ — одна из $$$k$$$ особых букв.
  3. После этого она удаляет все символы на таких позициях из пароля $$$s$$$ даже если $$$s_{i}$$$ — особая буква. Если таких позиций нет, программа выдает ошибку с очень громким звуком.

Например, пусть строка $$$s$$$ равна «abcdef», а особые буквы — «b» и «d». Если Хоссам запустит программу один раз, символы на позициях $$$1$$$ и $$$3$$$ будут удалены, так как они находятся перед особыми символами, и пароль станет равным «bdef». Если он запустит программу еще раз, она удалит символ на позиции $$$1$$$, и пароль станет «def». Хоссам поступит разумно, если не будет запускать программу в третий раз.

Хоссам хочет узнать, сколько максимум раз он может запустить программу на ноутбуке Хемоса, не разбудив его сигналом ошибки. Можете помочь ему?

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — исходную длину пароля.

Следующая строка содержит строку $$$s$$$, состоящую из $$$n$$$ строчных букв латинского алфавита — исходный пароль.

Следующая строка содержит целое число $$$k$$$ ($$$1 \le k \le 26$$$), а затем $$$k$$$ различных строчных букв латинского алфавита $$$c_1,c_2,\ldots,c_k$$$ — особые буквы.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите максимальное количество раз, которое Хоссам может запустить программу, не вызвав ошибку.

Пример
Входные данные
10
9
iloveslim
1 s
7
joobeel
2 o e
7
basiozi
2 s i
6
khater
1 r
7
abobeih
6 a b e h i o
5
zondl
5 a b c e f
6
shoman
2 a h
7
shetwey
2 h y
5
samez
1 m
6
mouraz
1 m
Выходные данные
5
2
3
5
1
0
3
5
2
0
Примечание

В первом наборе входных данных программу можно запустить $$$5$$$ раз: $$$\text{iloveslim} \to \text{ilovslim} \to \text{iloslim} \to \text{ilslim} \to \text{islim} \to \text{slim}$$$

Во втором наборе входных данных программу можно запустить $$$2$$$ раза: $$$\text{joobeel} \to \text{oel} \to \text{el}$$$

В третьем наборе входных данных программу можно запустить $$$3$$$ раза: $$$\text{basiozi} \to \text{bioi} \to \text{ii} \to \text{i}$$$.

В четвертом наборе входных данных программу можно запустить $$$5$$$ раз: $$$\text{khater} \to \text{khatr} \to \text{khar} \to \text{khr} \to \text{kr} \to \text{r}$$$

В пятом наборе входных данных программу можно запустить только раз: $$$\text{abobeih} \to \text{h}$$$

В шестом наборе программу нельзя запустить ни разу, так как пароль не содержит особых символов.