CF1670B.Dorms War

Hosssam decided to sneak into Hemose's room while he is sleeping and change his laptop's password. He already knows the password, which is a string $s$ of length $n$. He also knows that there are $k$ special letters of the alphabet: $c_1,c_2,\ldots, c_k$.

Hosssam made a program that can do the following.

1. The program considers the current password $s$ of some length $m$.
2. Then it finds all positions $i$ ($1\le i \lt m$) such that $s_{i+1}$ is one of the $k$ special letters.
3. Then it deletes all of those positions from the password $s$ even if $s_{i}$ is a special character. If there are no positions to delete, then the program displays an error message which has a very loud sound.

For example, suppose the string $s$ is "abcdef" and the special characters are 'b' and 'd'. If he runs the program once, the positions $1$ and $3$ will be deleted as they come before special characters, so the password becomes "bdef". If he runs the program again, it deletes position $1$, and the password becomes "def". If he is wise, he won't run it a third time.

Hosssam wants to know how many times he can run the program on Hemose's laptop without waking him up from the sound of the error message. Can you help him?

Hosssam 决定在 Hemose 睡觉时偷偷潜入他的房间，修改他笔记本电脑的密码。他早已知道了当前密码，该密码是一个长度为 $n$ 的字符串 $s$。他还知道字母表中有 $k$ 个特殊字母：$c_1,c_2,\ldots, c_k$。

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

1. 程序考虑当前密码 $s$（其长度为 $m$）；
2. 然后找出所有满足 $1\le i \lt m$ 的位置 $i$，使得 $s_{i+1}$ 是 $k$ 个特殊字母之一；
3. 接着，程序将这些位置 $i$ 上的字符全部从密码 $s$ 中删除（即使 $s_i$ 本身是特殊字符，也照删不误）。如果不存在任何可删除的位置，则程序会显示一条错误信息，该错误信息会发出非常响亮的声音。

例如，假设字符串 $s$ 为 "abcdef"，特殊字符为 'b' 和 'd'。若运行一次该程序，则位置 $1$ 和 $3$ 将被删除（因为它们分别位于特殊字符 'b' 和 'd' 之前），因此密码变为 "bdef"。若再次运行该程序，则位置 $1$ 被删除，密码变为 "def"。如果他足够明智，就不会再运行第三次。

Hosssam 想知道：他最多能对 Hemose 的笔记本电脑运行多少次该程序，而不会因错误信息的响声惊醒 Hemose？你能帮他解决这个问题吗？

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the initial length of the password.

The next line contains a string $s$ consisting of $n$ lowercase English letters — the initial password.

The next line contains an integer $k$ ($1 \le k \le 26$), followed by $k$ distinct lowercase letters $c_1,c_2,\ldots,c_k$ — the special letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print the maximum number of times Hosssam can run the program without displaying the error message, on a new line.

对于每个测试用例，在一行中输出 Hosssam 在不显示错误信息的情况下最多能运行该程序的次数。

In the first test case, the program can run $5$ times as follows: $\text{iloveslim} \to \text{ilovslim} \to \text{iloslim} \to \text{ilslim} \to \text{islim} \to \text{slim}$

In the second test case, the program can run $2$ times as follows: $\text{joobeel} \to \text{oel} \to \text{el}$

In the third test case, the program can run $3$ times as follows: $\text{basiozi} \to \text{bioi} \to \text{ii} \to \text{i}$.

In the fourth test case, the program can run $5$ times as follows: $\text{khater} \to \text{khatr} \to \text{khar} \to \text{khr} \to \text{kr} \to \text{r}$

In the fifth test case, the program can run only once as follows: $\text{abobeih} \to \text{h}$

In the sixth test case, the program cannot run as none of the characters in the password is a special character.

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

在第五个测试用例中，程序只能运行 $1$ 次，过程如下：$\text{abobeih} \to \text{h}$

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