CF1670B Dorms War

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 翻译