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

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

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

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.