← 返回题目列表

Codeforces · 1670/B

B. 宿舍战争

中文机器翻译题面 查看原题

Hosssam 决定趁 Hemose 睡觉时潜入他的房间并更改他笔记本电脑的密码。他已经知道密码,这是一个长度为 $$$n$$$ 的字符串 $$$s$$$。他还知道字母表中有 $$$k$$$ 特殊字母:$$$c_1,c_2,\ldots, c_k$$$。

Hosssam 制作了一个可以执行以下操作的程序。

1. 程序认为当前密码 $$$s$$$ 的长度为 $$$m$$$。
2. 然后它找到所有位置 $$$i$$$ ($$$1\le i<m$$$) 使得 $$$s_{i+1}$$$ 是 $$$k$$$ 特殊字母之一。
3. 然后,即使 $$$s_{i}$$$ 是特殊字符,它也会从密码 $$$s$$$ 中删除所有这些位置。如果没有要删除的位置,则程序会显示一条错误消息,并且声音很大。

例如,假设字符串 $$$s$$$ 为“abcdef”,特殊字符为“b”和“d”。如果他运行该程序一次,位置 $$$1$$$ 和 $$$3$$$ 将被删除,因为它们位于特殊字符之前,因此密码变为“bdef”。如果他再次运行该程序,它会删除位置$$$1$$$,并且密码变为“def”。如果他聪明的话,他不会再跑第三次了。

Hosssam 想知道他可以在 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 可以运行程序而不显示错误消息的最大次数。

示例

输入 #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

输出 #1

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}$$$

在第六个测试用例中,程序无法运行,因为密码中的所有字符都不是特殊字符。