题目描述

Hosssam 决定在 Hemose 睡觉时偷偷溜进他的房间，修改他笔记本的密码。他已经知道了密码，这个密码是一个长度为 $n$ 的字符串 $s$。他还知道有 $k$ 个特殊字母：$c_1,c_2,\ldots, c_k$。

Hosssam 编写了一个程序，可以执行如下操作：

1. 程序会读取当前长度为 $m$ 的密码 $s$。
2. 然后找到所有满足 $1\le i < m$ 的位置 $i$，使得 $s_{i+1}$ 是 $k$ 个特殊字母之一。
3. 然后从密码 $s$ 中删除所有这些位置的字符，即使 $s_i$ 本身是特殊字符也会被删除。如果没有可以删除的位置，程序会显示一个带有很大声音的错误信息。

例如，假设字符串 $s$ 是 "abcdef"，特殊字符是 'b' 和 'd'。如果运行一次程序，位置 $1$ 和 $3$ 会被删除，因为它们分别在特殊字符前面，所以密码变为 "bdef"。如果再运行一次程序，会删除位置 $1$，密码变为 "def"。如果他聪明的话，就不会再运行第三次了。

Hosssam 想知道，他最多可以在 Hemose 的笔记本上运行多少次程序，而不会因为错误信息的声音把 Hemose 吵醒。你能帮帮他吗？

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是 $t$ 组测试数据。

每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示密码的初始长度。

第二行包含一个由 $n$ 个小写英文字母组成的字符串 $s$，表示初始密码。

第三行包含一个整数 $k$（$1 \le k \le 26$），后面跟着 $k$ 个互不相同的小写字母 $c_1,c_2,\ldots,c_k$，表示特殊字母。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出 Hosssam 最多可以运行程序的次数，每个结果占一行。

说明/提示

在第一个测试用例中，程序最多可以运行 $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}$。

在第六个测试用例中，程序无法运行，因为密码中没有任何字符是特殊字符。

由 ChatGPT 4.1 翻译

样例

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