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}$$$
在第六个测试用例中,程序无法运行,因为密码中的所有字符都不是特殊字符。