Dorms War
Contest: Codeforces Round 788 (Div. 2)
Difficulty rating: 1100
Tags: brute force, implementation, strings

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<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?

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
5
2
3
5
1
0
3
5
2
0

Editorial:
Let's consider the non-special characters as '0' and special characters as '1' since they are indistinguishable. So now the problem is that we have a binary string, where each '1' character removes the character before it each time the program is run.
The trivial case is when there is only one '1' character, the answer then is just the number of '0' characters before it.
But what if there is more than one '1' character? lets take for example when there are two '1' characters as follows: $$$00000010001\to 000001001\to 0000101\to 00011\to 001\to 01\to 1$$$
The observation here is that when the first '1' character from the right reached the second '1', it acts as if it just replaced its place, so we can say that each '1' character replaces another '1' as soon as it reaches it.
So we can partition the binary string into small partitions where each partition contains only one '1' character that is the rightmost character in the partition.
For example, the string $$$00010000001011$$$ can be partitioned into: $$$(0001),(0000001),(01),(1)$$$
We first calculate the amount of time each partition requires to remove all the '0' characters before it, which is basically the number of '0' characters before it. Each partition except for the first partition requires one more second to replace the '1' character in the previous partition.
So the answer is the maximum time required among all the partitions.