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.

The program considers the current password $s$ of some length $m$.

Then it finds all positions $i$ ($1\le i<m$) such that $s_{i+1}$ is one of the $k$ special letters.

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

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

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


-----Examples-----

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
Output
5
2
3
5
1
0
3
5
2
0


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

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Implementation

Complete search


Solutions:
import sys
DEBUG = False

def transform(s, chars):
	n_steps = 0
	new_s

def check(s, chars):
	chars = set(chars)
	max_len = 0
	cur_len = 0
	prev_was = 0
	for c in s:
		if not c in chars:
			cur_len += 1
		else:
			max_len = max(max_len, cur_len + prev_was)
			cur_len = 0
			prev_was = 1
	print(max_len)

def main(f):
	t = int(f.readline())
	for i in range(t):
		n = int(f.readline())
		s = f.readline().strip()
		special_chars = f.readline().split()[1:]
		check(s, special_chars)
if DEBUG:
	f = open('input.txt', 'r')
else:
	f = sys.stdin
main(f)
f.close()


import sys
input = sys.stdin.readline
for t in range(int(input())):
	n = int(input())
	s = input()
	k = input().split()[1:]
	m = e = 0
	for i in range(n):
		if s[i] in k:
			e = max(e, i - m)
			m = i
	print(e)


import sys
input = sys.stdin.readline
for i in range(int(input())):
	lenn = int(input())
	string = input()
	inp = input().split()
	(lenn1, special) = (inp[0], inp[1:])
	len_subs = []
	count = 0
	huh = 0
	first = -1
	for i in range(lenn):
		if string[i] in special:
			if first == -1:
				first = i
				huh = 1
			else:
				huh = 0
				second = i
				len_subs.append(second - first)
				first = i
			if huh == 1:
				len_subs.append(i)
	try:
		print(max(len_subs))
	except:
		print(0)


import sys
I = sys.stdin.readline
for _ in range(int(I())):
	n = int(I())
	s = I().strip()
	lst = set(I().split()[1:])
	(res, cur) = (0, 0)
	for c in s:
		if c in lst:
			res = max(res, cur)
			cur = 1
		else:
			cur += 1
	print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	k = set(input().split())
	p = 0
	c = 0
	m = 0
	for i in range(n - 1):
		if s[i + 1] not in k:
			c += 1
		else:
			m = max(m, c + 1)
			c = 0
	print(m)


from sys import stdin, stdout
import collections
import math

def solve():
	return

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input().strip()
		k = input().split()
		k.pop(0)
		k = set(k)
		g = []
		for i in range(n):
			if s[i] in k:
				g.append(i)
		ans = 0
		if g and g[0] != 0:
			g.insert(0, 0)
		for i in range(len(g) - 1):
			ans = max(ans, g[i + 1] - g[i])
		print(ans)
	return
input = stdin.readline
main()


import sys
input = sys.stdin.readline

def solve():
	N = int(input())
	P = input()
	S = set(input().split()[1:])
	specials = []
	for (i, c) in enumerate(P):
		if c in S:
			specials.append(i)
	lifes = []
	for i in range(len(specials)):
		if len(lifes) == 0:
			lifes.append(specials[i])
		else:
			lifes.append(max(lifes[-1], specials[i] - specials[i - 1]))
	if not lifes:
		return 0
	else:
		return lifes[-1]
for _ in range(int(input())):
	print(solve())


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(int(1000000000.0))

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
for _ in range(ii()):
	n = ii()
	s = input().strip()
	a = input().split()
	a = set(a)
	(cnt, ans) = (0, 0)
	for i in s:
		if i in a:
			ans = max(ans, cnt)
			cnt = 1
		else:
			cnt += 1
	print(ans)


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(2 * 10 ** 5)
input = sys.stdin.readline

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
fact = [1]
ANS = []
for t in range(int(input())):
	n = int(input())
	a = input().strip()
	b = input().strip().split()
	b = set(b[1:])
	ans = 0
	c = 0
	start = p
	for i in range(n - 1, -1, -1):
		if a[i] in b:
			start = i - 1
			break
	if start == p:
		print(0)
	else:
		for i in range(start, -1, -1):
			c += 1
			ans = max(c, ans)
			if a[i] in b:
				c = 0
		print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = list(input().split())[1:]
	c = set(c)
	t = 0
	m = 0
	for i in range(n):
		if s[i] in c:
			m = max(m, t)
			t = 1
		else:
			t += 1
	print(m)


import sys
T = int(sys.stdin.readline().strip())
for t in range(T):
	n = int(sys.stdin.readline().strip())
	s = sys.stdin.readline().strip()
	tmp = sys.stdin.readline().strip().split(' ')
	delete = set(tmp[1:])
	ans = 0
	pre = 0
	for c in s:
		if c not in delete:
			pre += 1
		else:
			ans = max(ans, pre)
			pre = 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, s) = (int(input()), input())
	spe = set([*input().split()][1:])
	pre = res = 0
	for i in range(n):
		if s[i] in spe:
			res = max(res, i - pre)
			pre = i
	print(res)


def solve() -> int:
	n = int(input())
	password = input()
	(_, *special) = input().split()
	special = set(special)
	result = None
	current = 0
	for char in password:
		if char in special:
			if result is None:
				result = current
			else:
				result = max(result, current + 1)
			current = 0
		else:
			current += 1
	if result is None:
		result = 0
	return result
results = []
for _ in range(int(input())):
	results.append(str(solve()))
print('\n'.join(results))


import sys
input = sys.stdin.readline
for f in range(int(input())):
	(n, s) = (int(input()), input())
	d = set([*input().split()][1:])
	p = r = 0
	for i in range(n):
		if s[i] in d:
			r = max(r, i - p)
			p = i
	print(r)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	dlugosc = int(input())
	slowo = input()
	unikat = set(input().split()[1:])
	temp = 0
	odp = 0
	for i in range(dlugosc):
		if slowo[i] in unikat:
			odp = max(odp, temp)
			temp = 1
		else:
			temp += 1
	print(odp)


import sys
input = sys.stdin.readline
for i in range(int(input())):
	n = int(input())
	pas = input()
	a = set(list(input().split())[1:])
	z = m = 0
	for j in range(n):
		if pas[j] in a:
			m = max(m, z)
			z = 1
		else:
			z += 1
	print(m)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()[:-1]
	d = set(input()[:-1].split()[1:])
	m = 0
	c = 0
	for i in range(n):
		if s[i] in d:
			m = max(m, c)
			c = 0
		c += 1
	print(m)


import math
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	se = set([*input().split()][1:])
	mx = 0
	cur = 0
	for i in range(n):
		if s[i] in se:
			mx = max(mx, i - cur)
			cur = i
	print(mx)


import sys
input = sys.stdin.readline
for f in range(int(input())):
	n = int(input())
	s = input()
	d = set([*input().split()][1:])
	c = ans = 0
	for i in range(n):
		if s[i] in d:
			ans = max(ans, i - c)
			c = i
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	cl = set(input().split()[1:])
	(ans, prev) = (0, 0)
	for i in s:
		if i not in cl:
			prev += 1
		else:
			ans = max(ans, prev)
			prev = 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	sp = set(input().split()[1:])
	p = 0
	ans = 0
	for i in range(n):
		if s[i] in sp:
			ans = max(ans, i - p)
			p = i
	print(ans)


import sys, math
INF = 1 << 100
mod = 1000000007
input = lambda : sys.stdin.readline().rstrip()
li = lambda : list(map(int, input().split()))
t = int(input())
out = []
for _ in range(t):
	N = int(input())
	S = input()
	C = input().split()
	st = set(C[1:])
	lst = []
	if S[0] in st:
		lst.append(1)
	else:
		lst.append(0)
	x = 0
	for i in range(1, N):
		if S[i] in st:
			if not lst[-1]:
				lst.append(1)
			else:
				x = 1
		else:
			lst.append(0)
	lst2 = [x]
	cnt = 0
	for i in range(len(lst)):
		if lst[i]:
			lst2.append(cnt)
			cnt = 1
		else:
			cnt += 1
	out.append(max(lst2))
for o in out:
	print(o)


import math as m
i = input()
inp = []
inp2 = []
for a in range(0, int(i)):
	input()
	inp += [input()]
	inp2 += [input()]

def maxx(arr):
	if arr == []:
		return 0
	return max(arr)
for i in range(len(inp)):
	s = inp[i]
	S = inp2[i].split()
	count = 0
	a = []
	for c in s:
		if c in S:
			a += [count]
			count = 1
		else:
			count += 1
	print(maxx(a))


import sys
input = sys.stdin.readline
for jj in range(int(input())):
	(n, s) = (int(input()), input())
	arr = set([*input().split()][1:])
	a = ans = 0
	for i in range(n):
		if s[i] in arr:
			ans = max(ans, i - a)
			a = i
	print(ans)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	k = set(input().split()[1:])
	ans = marker = 0
	for i in range(n):
		if s[i] in k:
			ans = max(ans, i - marker)
			marker = i
	print(ans)


from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
from functools import lru_cache
import sys
DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
MOD = 10 ** 9 + 7
input = sys.stdin.readline
t = int(input())

def solve():
	n = int(input())
	s = input().strip('\n')
	k = [x for x in input().strip('\n').split(' ')]
	kn = int(k[0])
	k = set(k[1:])
	spec = [0]
	for i in range(n):
		if s[i] in k:
			spec.append(i)
	if not spec:
		print(0)
		return
	best = -inf
	for i in range(1, len(spec)):
		best = max(best, spec[i] - spec[i - 1])
	print(max(best, 0))
while t:
	solve()
	t -= 1


import sys
sys.setrecursionlimit(2 * 10 ** 5)
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	s = input().strip()
	arr = input().strip().split()
	dict = {}
	for j in range(1, len(arr)):
		dict[arr[j]] = 1
	st = 0
	md = 0
	for j in range(n):
		if s[j] in dict.keys():
			if j - st > md:
				md = j - st
			st = j
	print(md)


import math
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	special = [x for x in input().split()]
	k = int(special[0])
	special = set(special[1:])
	current_pos = -1
	previous_pos = -1
	difference = 0
	ans = -100
	for i in range(n):
		if s[i] in special:
			previous_pos = current_pos
			current_pos = i
			if previous_pos == -1:
				difference = current_pos
			else:
				difference = abs(current_pos - previous_pos)
		ans = max(difference, ans)
	print(ans)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	password = sys.stdin.readline()
	specials = list(map(str, sys.stdin.readline().split()))
	specials.pop(0)
	ans = 0
	intervals = [0]
	begin = 0
	for (index, letter) in enumerate(password):
		if letter in specials:
			intervals.append(index - begin)
			begin = index
	print(max(intervals))


import sys
input = sys.stdin.readline

def check(l1, l2):
	for i in l1:
		if i in l2:
			return False
			break
	else:
		return True
tc = int(input())
for _ in range(tc):
	n = int(input())
	s = input()
	k = list(s)
	c = list(input().split())
	cnt = 0
	i = 0
	if check(c, k) == True:
		print(0)
	else:
		l = []
		a = 0
		i = 0
		for i in range(len(s)):
			if s[i] in c and a == 0:
				l.append(i)
				a += 1
			if s[i] in c and a != 0:
				for j in range(i + 1, len(s)):
					if s[j] in c:
						l.append(j - i)
						break
		print(max(l))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input().strip()
	arr = list(input().split())
	bag = set()
	for c in arr[1:]:
		bag.add(c)
	cnt = ans = 0
	dis = {}
	tmp = []
	for i in range(n):
		if s[i] in bag:
			ans = max(ans, cnt)
			if cnt not in dis:
				dis[cnt] = 0
			tmp.append(cnt)
			dis[cnt] += 1
			cnt = 0
		else:
			cnt += 1
	if not tmp:
		return ans
	if dis[ans] > 1:
		return ans + 1
	else:
		return ans if tmp[0] == ans else ans + 1
for _ in range(int(input())):
	print(solve())


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	string = sys.stdin.readline().split()[0]
	items = sys.stdin.readline().split()[1:]
	hashmap = [0] * 27
	for i in items:
		hashmap[ord(i) - ord('a')] = 1
	maxi = 0
	pre = 0
	for (index, val) in enumerate(string):
		if hashmap[ord(val) - ord('a')]:
			maxi = max(maxi, index - pre)
			pre = index
	print(maxi)


import sys
input = sys.stdin.readline
T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	s = input()
	ss = [False for i in range(n)]
	(k_, *c) = list(input().split())
	f = set(c)
	for i in range(n):
		if s[i] in f:
			ss[i] = True
	cmax = 0
	count = -2 * n
	for l in ss[::-1]:
		count += 1
		if l:
			cmax = max(cmax, count)
			count = 0
	cmax = max(cmax, count)
	print(cmax)


from sys import stdin

def input():
	return stdin.readline().strip()

def read_int():
	return int(input())

def read_ints():
	return map(int, input().split())
t = read_int()
for case_num in range(t):
	n = read_int()
	s = input()
	special = input().split()[1:]
	svec = [False] * 26
	for ch in special:
		svec[ord(ch) - ord('a')] = True
	x = [i for (i, ch) in enumerate(s) if svec[ord(ch) - ord('a')]]
	last = 0
	ans = 0
	for i in x:
		ans = max(ans, i - last)
		last = i
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	l = input()
	a = set(map(str, input().split()))
	o = 0
	maxx = 0
	for j in range(n):
		if l[j] in a:
			maxx = max(maxx, o)
			o = 1
		else:
			o += 1
	print(maxx)


import sys
from collections import defaultdict
MYPC = False
if MYPC:
	sys.stdin = open('in.txt', 'r')
	sys.stdout = open('out.txt', 'w')
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
from collections import defaultdict
t = int(input())
while t:
	t -= 1
	b = int(input())
	s = input()
	tej = input()
	dic = defaultdict(bool)
	for j in range(1, len(tej)):
		dic[tej[j]] = True
	ind = 0
	par_ans = 0
	for j in range(0, b):
		if dic[s[j]]:
			par_ans = max(par_ans, j - ind)
			ind = j
	print(par_ans)


from collections import *
ALL = []
for _ in ' ' * int(input()):
	n = int(input())
	s = input()
	a = input().split()
	k = int(a[0])
	a = a[1:]
	d = defaultdict(int)
	for i in a:
		d[i] = 1
	v = []
	c = 0
	mx = 0
	c1 = 0
	for i in s:
		if i in d:
			v.append(c)
			c = 0
		else:
			c += 1
	for i in v:
		if i > mx:
			mx = i
			c1 = 1
		elif mx == i:
			c1 += 1
	out = 0
	if len(v) and mx >= 0:
		if c1 > 1 or v[0] < mx:
			out = mx + 1
		else:
			out = mx
	ALL.append(out)
print(*ALL, sep='\n')


n = int(input())
datas = []
for i in range(n):
	l = int(input())
	s = input()
	data = input().split()
	letters = data[1:]
	datas.append((s, letters))

def solve(s, letters):
	letters = set(letters)
	i = 0
	m = None
	c = 0
	for l in s:
		if l in letters:
			if m is None:
				m = i
			else:
				if c:
					i += 1
				m = max(m, i)
			i = 0
			c += 1
		if l not in letters:
			i += 1
	print(m or 0)
for (s, letters) in datas:
	solve(s, letters)


import sys
import math
from math import gcd, sqrt, log2, ceil, floor
import heapq as hq
from bisect import bisect_right, bisect_left, bisect
import itertools
from sys import stdin, stdout, setrecursionlimit
MOD = int(1000000000.0) + 7
alp = 'abcdefghijklmnopqrstuvwxyz'
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	s = str(stdin.readline().strip('\n'))
	b = list(stdin.readline().strip('\n'))
	k = int(b[0])
	d = {}
	for i in b[1:]:
		if i != ' ':
			d[i] = 1
	ss = ''
	for i in s:
		if i in d:
			ss += '1'
		else:
			ss += '0'
	ix = []
	for i in range(n):
		if ss[i] == '1':
			ix.append(i)
	ix = [0] + ix
	ans = 0
	for i in range(len(ix) - 1):
		ans = max(ans, ix[i + 1] - ix[i])
	print(ans)