Dorms War Codeforces Solution | Codeforces Problem Solution 2022

Dorms War Codeforces Solution | Codeforces Problem Solution 2022

B. Dorms War

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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: 𝑐1,𝑐2,…,𝑐𝑘$c_1,c_2,\dots ,c_k$.

Hosssam made a program that can do the following.

Solution Click Below:-  CLICK HERE

1. The program considers the current password 𝑠$s$ of some length 𝑚$m$.
2. Then it finds all positions 𝑖$i$ (1≤𝑖<𝑚$1\le i<m$) such that 𝑠𝑖+1$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.

Prof. Slim Codeforces Solution | Codeforces Problem Solution 2022

Dorms War Codeforces Solution | Codeforces Problem Solution 2022

Where is the Pizza? Codeforces Solution | Codeforces Problem Solution 2022

Very Suspicious Codeforces Solution | Codeforces Problem Solution 2022

Hemose on the Tree Codeforces Solution | Codeforces Problem Solution 2022

Jee, You See? Codeforces Solution | Codeforces Problem Solution 2022

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$1$ and 3$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$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

The first line contains a single integer 𝑡$t$ (1≤𝑡≤105$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≤𝑛≤105$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≤𝑘≤26$1\le k\le 26$), followed by 𝑘$k$ distinct lowercase letters 𝑐1,𝑐2,…,𝑐𝑘$c_1,c_2,\dots ,c_k$ — the special letters.

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

Output

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

Join Now for Solution:-