Given an array of strings arr[] of size n, a string str and an integer k. The task is to find the count of strings in arr[] whose prefix of length k matches with the k-length prefix of str.
Example 1:
Input:
n = 6
arr[] = {“abba”, “abbb”, “abbc”, “abbd”, 
“abaa”, “abca”}
str = “abbg”
k = 3
Output: 
4 
Explanation:
“abba”, “abbb”, “abbc” and “abbd” have their prefix of length 3 equal to 3-length prefix of str i.e., "abb".
Example 2:
Input:
n = 3
arr[] = {“geeks”, “geeksforgeeks”, “forgeeks”}
str = “geeks”
k = 2
Output: 
2
Explanation:
“geeks” and “geeksforgeeks” have their prefix of length 2 equal to 2-length prefix of str i.e., "ge".
Your Task:  
You don't need to read input or print anything. Your task is to complete the function klengthpref() which takes the array of strings arr[], its size n and an integer k, a string str as input parameters and returns the count of strings in arr[] whose prefix of length k matches with the k length prefix of str.
Expected Time Complexity: O(n*l) where l is the length of the longest word in arr[].
Expected Auxiliary Space: O(n*l) where l is the length of the longest word in arr[].
Constraints:
1 <= n <= 1000
1^{ }<= |arr[i]| , |str| <= 1000
1 <= k <= 1000
arr[i], str must contain only lowercase English alphabets

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(n*l) where l is the length of the longest word in arr[].
Expected Auxiliary Space: O(n*l) where l is the length of the longest word in arr[].

Starter code:
#User function Template for python3



class Solution:

    def klengthpref(self,arr,n,k,s):

        # return list of words(str) found in the board

Solutions:
class Solution:

	def klengthpref(self, arr, n, k, s):
		res = 0
		t = s[:k]
		for i in arr:
			if i[:k] == t:
				res += 1
		return res


class Solution:

	def klengthpref(self, arr, n, k, s):
		c = 0
		a = s[:k]
		for i in arr:
			if i.startswith(a):
				c += 1
		return c


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Solution:
	root = TrieNode()

	def insert(self, root, key):
		for e in key:
			idx = ord(e) - ord('a')
			if not root.children[idx]:
				root.children[idx] = TrieNode()
			root = root.children[idx]
		root.isEndOfWord = True

	def prefixPresent(self, root, key):
		for e in key:
			idx = ord(e) - ord('a')
			if not root.children[idx]:
				return False
			root = root.children[idx]
		return root.isEndOfWord

	def klengthpref(self, arr, n, k, s):
		prefix = s[0:k]
		result = []
		self.insert(self.root, prefix)
		for str in arr:
			if len(str) >= k:
				if self.prefixPresent(self.root, str[0:k]):
					result.append(str)
		return len(result)


class Solution:

	def klengthpref(self, arr, n, k, s):
		count = 0
		for i in range(len(arr)):
			if len(arr[i]) >= k and arr[i][0:k] == s[0:k]:
				count += 1
		return count


class Solution:

	def klengthpref(self, arr, n, k, s):
		c = 0
		f = ''
		s = s[:k]
		for i in range(n):
			f += arr[i]
			if f[:k] == s:
				c += 1
			f = ''
		return c


class Solution:

	def klengthpref(self, arr, n, k, s):
		match_count = 0
		for i in range(n):
			current_str = arr[i]
			if len(arr[i]) >= k:
				if current_str[:k] == s[:k]:
					match_count += 1
		return match_count


class Solution:

	def klengthpref(self, arr, n, k, s):
		cnt = 0
		m = s[0:k]
		for x in arr:
			if x[0:k] == m:
				cnt += 1
		return cnt


class Solution:

	def klengthpref(self, arr, n, k, s):
		cnt = 0
		m = s[0:k]
		for i in range(0, n):
			l = arr[i][0:k]
			if l == m:
				cnt = cnt + 1
		return cnt


class Solution:

	def klengthpref(self, arr, n, k, s):
		ct = 0
		for ar in arr:
			if s[:k] == ar[:k]:
				ct += 1
		return ct


class Solution:

	def klengthpref(self, arr, n, k, s):
		ans = 0
		for i in arr:
			if i[0:k] == s[0:k]:
				ans += 1
		return ans


class TrieNode:

	def __init__(self):
		self.kids = [None] * 26
		self.freq = 0

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, s):
		_in = 0
		cur = self.root
		for i in range(len(s)):
			_in = ord(s[i]) - ord('a')
			if not cur.kids[_in]:
				cur.kids[_in] = TrieNode()
			cur.kids[_in].freq += 1
			cur = cur.kids[_in]

	def find(self, s, k):
		_in = 0
		count = 0
		cur = self.root
		for i in range(len(s)):
			_in = ord(s[i]) - ord('a')
			if cur.kids[_in] == None:
				return 0
			cur = cur.kids[_in]
			count += 1
			if count == k:
				return cur.freq
		return 0

class Solution:

	def klengthpref(self, arr, n, k, s):
		t = Trie()
		for i in arr:
			t.insert(i)
		return t.find(s, k)


class Solution:

	def klengthpref(self, arr, n, k, s):
		c = 0
		if k > len(s):
			return 0
		for i in arr:
			if len(i) < k:
				continue
			if i[:k] == s[:k]:
				c += 1
		return c


class Node:

	def __init__(self):
		self.arr = [None] * 26
		self.freq = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return Node()

	def insert(self, name):
		cur = self.root
		n = len(name)
		for i in range(n):
			alphaIndex = ord('a') - ord(name[i])
			if cur.arr[alphaIndex] == None:
				cur.arr[alphaIndex] = self.getNode()
			cur.arr[alphaIndex].freq += 1
			cur = cur.arr[alphaIndex]

	def find(self, name, k):
		cur = self.root
		for i in range(min(k, len(name))):
			alphaIndex = ord('a') - ord(name[i])
			if cur.arr[alphaIndex] == None:
				break
			cur = cur.arr[alphaIndex]
		return cur.freq

class Solution:

	def klengthpref(self, arr, n, k, s):
		root = Trie()
		for name in arr:
			root.insert(name)
		return root.find(s, k)


class Solution:

	def klengthpref(self, arr, n, k, s):
		count = 0
		for word in range(len(arr)):
			wordd = arr[word]
			if wordd[0:k] == s[0:k]:
				count += 1
		return count


class Trie:

	def __init__(self):
		self.child = {}
		self.pc = 0

class Solution:

	def klengthpref(self, arr, n, k, s):

		def insert(root, word):
			curr = root
			for ch in word:
				if ch not in curr.child:
					curr.child[ch] = Trie()
					curr = curr.child[ch]
				else:
					curr = curr.child[ch]
				curr.pc += 1

		def prefixcnt(root, prefix):
			curr = root
			for ch in prefix:
				if ch not in curr.child:
					return 0
				curr = curr.child[ch]
			return curr.pc
		root = Trie()
		for word in arr:
			insert(root, word)
		prefix = s[:k]
		ans = prefixcnt(root, prefix)
		return ans


class Solution:

	def klengthpref(self, arr, n, k, s):
		count = 0
		s1 = s[:k]
		for i in range(n):
			s2 = arr[i]
			if s1 == s2[:k]:
				count += 1
		return count


class Solution:

	def klengthpref(self, arr, n, k, s):
		prefix = s[:k]
		count = 0
		for name in arr:
			if prefix == name[:len(prefix)]:
				count += 1
		return count


class Solution:

	def klengthpref(self, arr, n, k, s):
		tempString = s[:k]
		count = 0
		for i in arr:
			if i.startswith(tempString):
				count += 1
		return count


class Solution:

	def klengthpref(self, arr, n, k, s):

		class TrieNode:

			def __init__(self):
				self.child = {}
				self.Eow = False
				self.c = 1

		def insert(word, Trie):
			for w in word:
				if w not in Trie.child:
					Trie.child[w] = TrieNode()
				else:
					Trie.child[w].c += 1
				Trie = Trie.child[w]
			Trie.Eow = True

		def prefix_search_c(s, k, Trie):
			cnt = 0
			for ch in range(k):
				if s[ch] in Trie.child:
					Trie = Trie.child[s[ch]]
					cnt += 1
			if cnt:
				return Trie.c
			else:
				return cnt
		Trie = TrieNode()
		for word in arr:
			insert(word, Trie)
		return prefix_search_c(s, k, Trie)


class TrieNode:

	def __init__(self):
		self.links = [None] * 26
		self.cp = 0

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		curr = self.root
		for ele in key:
			if not curr.links[ord(ele) - ord('a')]:
				curr.links[ord(ele) - ord('a')] = TrieNode()
			curr = curr.links[ord(ele) - ord('a')]
			curr.cp += 1

	def countPrefix(self, key):
		curr = self.root
		for ele in key:
			if not curr.links[ord(ele) - ord('a')]:
				return 0
			curr = curr.links[ord(ele) - ord('a')]
		return curr.cp

class Solution:

	def klengthpref(self, arr, n, k, s):
		t = Trie()
		for ele in arr:
			t.insert(ele)
		return t.countPrefix(s[:k])


class Solution:

	def klengthpref(self, arr, n, k, s):
		di = {}
		for word in arr:
			curr = di
			for i in word:
				if i not in curr:
					curr[i] = {}
				curr = curr[i]
			curr['end'] = curr.get('end', 0) + 1
		curr = di
		ind = 0
		while ind < k:
			curr = curr[s[ind]]
			ind += 1

		def cccc(curr):
			count = 0
			for i in curr.keys():
				if i == 'end':
					count += curr['end']
				else:
					count += cccc(curr[i])
			return count
		return cccc(curr)


class Solution:

	def klengthpref(self, words, n, k, stri):
		pref = stri[:k]
		trie = {}
		next = trie
		for word in words:
			for c in word:
				if c not in next:
					next[c] = {}
				next = next[c]
			next['end word'] = next.get('end word', 0) + 1
			next = trie
		for c in pref:
			if c in next:
				next = next[c]
			else:
				return 0
		return self.trie(next)

	def trie(self, next):
		out1 = 0
		for key in next:
			if key != 'end word':
				out1 += self.trie(next[key])
			else:
				out1 += next['end word']
		return out1


class Node:

	def __init__(self):
		self.child = [None] * 26
		self.cntpre = 0
		self.end = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return Node()

	def charIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		size = len(key)
		node = self.root
		for i in range(size):
			index = self.charIndex(key[i])
			if node.child[index] == None:
				node.child[index] = self.getNode()
			node = node.child[index]
			node.cntpre += 1
		node.end += 1

	def search(self, key):
		size = len(key)
		node = self.root
		for i in range(size):
			index = self.charIndex(key[i])
			if node.child[index] == None:
				return
			node = node.child[index]
		return node.cntpre

class Solution:

	def klengthpref(self, arr, n, k, s):
		root = Trie()
		for i in arr:
			root.insert(i)
		return root.search(s[:k])


class Solution:

	def klengthpref(self, arr, n, k, s):
		subs = s[:k]
		res = [i for i in arr if subs == i[:k]]
		return len(res)


class Trie:

	def __init__(self):
		self.children = {}
		self.eow = False
		self.count = 0
		self.starts = 0

class Solution:

	def create(self, word):
		cur = self.root
		for ch in word:
			if ch not in cur.children:
				cur.children[ch] = Trie()
			cur = cur.children[ch]
			cur.starts += 1
		cur.count += 1
		cur.eow += 1

	def travel(self, word, k):
		cur = self.root
		for i in range(k):
			if word[i] in cur.children:
				cur = cur.children[word[i]]
			else:
				return None
		return cur

	def klengthpref(self, arr, n, k, s):
		self.root = Trie()
		for word in arr:
			self.create(word)
		cur = self.travel(s, k)
		if cur is None:
			return 0
		else:
			return cur.starts


class Solution:

	def klengthpref(self, arr, n, k, s):

		def match(s1, t, te):
			count = 0
			for i in range(te):
				if s1[i] == t[i]:
					count += 1
				else:
					break
			if count == te:
				return True
			return False

		def original(arr, s, k):
			res = 0
			for i in range(len(arr)):
				if match(arr[i], s, k):
					res += 1
			return res
		return original(arr, s, k)


class Solution:

	def klengthpref(self, arr, n, k, s):
		count = 0
		for a in arr:
			if a[0:k] == s[0:k]:
				count = count + 1
		return count


class Solution:

	def klengthpref(self, arr, n, k, s):
		S = s[0:k]
		ans = [word for word in arr if S in word]
		return len(ans)


class Solution:

	def klengthpref(self, arr, n, k, s):
		temp = s[:k]
		ans = 0
		for word in arr:
			if word[:k] == temp:
				ans += 1
		return ans


class Solution:

	def klengthpref(self, arr, n, k, s):
		res = 0
		for word in arr:
			if word[:k] == s[:k]:
				res += 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = []
		for x in range(n):
			s1 = input()
			arr.append(s1)
		k = int(input())
		s = input()
		obj = Solution()
		print(obj.klengthpref(arr, n, k, s))


class Solution:

	def klengthpref(self, arr, n, k, s):
		l = []
		for i in arr:
			if i[0:k] == s[0:k]:
				l.append(i)
		return len(l)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = []
		for x in range(n):
			s1 = input()
			arr.append(s1)
		k = int(input())
		s = input()
		obj = Solution()
		print(obj.klengthpref(arr, n, k, s))


class Solution:

	def klengthpref(self, arr, n, k, s):
		a = s[:k]
		c = 0
		for i in range(n):
			if len(arr[i]) < k:
				continue
			t = arr[i]
			b = t[:k]
			if a == b:
				c += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = []
		for x in range(n):
			s1 = input()
			arr.append(s1)
		k = int(input())
		s = input()
		obj = Solution()
		print(obj.klengthpref(arr, n, k, s))


class Solution:

	def klengthpref(self, arr, n, k, s):
		prefix = ''.join(s[0:k])
		c = 0
		for i in arr:
			if prefix in i:
				c += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = []
		for x in range(n):
			s1 = input()
			arr.append(s1)
		k = int(input())
		s = input()
		obj = Solution()
		print(obj.klengthpref(arr, n, k, s))


class Solution:

	def klengthpref(self, arr, n, k, s):
		count = 0
		substring_slice = s[0:k]
		for word in arr:
			if word[0:k] == substring_slice:
				count += 1
		return count


class Solution:

	def klengthpref(self, arr, n, k, s):
		ans = 0
		for i in arr:
			cnt = 0
			x = 0
			j = 0
			while x < k and j < len(i):
				if i[j] == s[x]:
					cnt += 1
				x += 1
				j += 1
			if cnt == k:
				ans += 1
		return ans


class TrieNode:

	def __init__(self):
		self.children = dict()
		self.count = 0

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		current = self.root
		for char in key:
			if char not in current.children:
				current.children[char] = TrieNode()
			current.children[char].count += 1
			current = current.children[char]

	def search(self, key):
		current = self.root
		for char in key:
			if char not in current.children:
				return current.count
			current = current.children[char]
		return current.count

class Solution:

	def klengthpref(self, arr, n, k, s):
		trie = Trie()
		for word in arr:
			trie.insert(word)
		return trie.search(s[:k])


from collections import defaultdict

class Solution:

	def klengthpref(self, arr, n, k, s):
		map = defaultdict(int)
		for s1 in arr:
			map[s1[:k]] += 1
		return map[s[:k]]


class Solution:

	def klengthpref(self, arr, n, k, s):
		lk = s[:k]
		count = 0
		for i in range(n):
			st = arr[i]
			st = st[:k]
			if lk == st:
				count += 1
		return count


class TrieNode:

	def __init__(self):
		self.links = [None] * 26
		self.countEndsWith = 0
		self.countPrefix = 0

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		node = self.root
		for i in range(len(word)):
			x = ord(word[i]) - ord('a')
			if not node.links[x]:
				node.links[x] = TrieNode()
			node = node.links[x]
			node.countPrefix += 1
		node.countEndsWith += 1

	def CountWordsStartwith(self, word):
		node = self.root
		for i in range(len(word)):
			x = ord(word[i]) - ord('a')
			if not node.links[x]:
				return 0
			node = node.links[x]
		return node.countPrefix

	def CountWordsEqualto(self, word):
		node = self.root
		for i in range(len(word)):
			x = ord(word[i]) - ord('a')
			if not node.links[x]:
				return 0
			node = node.links[x]
		return node.countEndsWith

	def Erase(self, word):
		node = self.root
		for i in range(len(word)):
			x = ord(word[i]) - ord('a')
			if not node.links[x]:
				node.links[x] = TrieNode()
			node = node.links[x]
			node.countPrefix -= 1
		node.countEndsWith -= 1

class Solution:

	def klengthpref(self, arr, n, k, s):
		TR = Trie()
		for i in arr:
			TR.insert(i)
		return TR.CountWordsStartwith(s[:k])


class TrieNode:

	def __init__(self, char):
		self.char = char
		self.children = {}
		self.count = 1

class Solution:

	def TrieInsert(root, word):
		node = root
		for w in word:
			if w in node.children:
				node = node.children[w]
				node.count += 1
			else:
				new_node = TrieNode(w)
				node.children[w] = new_node
				node = new_node
		node.end = True

	def query(root, word):
		node = root
		if word[0] not in node.children:
			return 0
		for w in word:
			if w in node.children:
				node = node.children[w]
			else:
				break
		prefix = node.count
		return prefix

	def klengthpref(self, arr, n, k, s):
		root = TrieNode('0')
		for word in arr:
			Solution.TrieInsert(root, word)
		token = s[:k]
		ans = Solution.query(root, token)
		return ans


class Solution:

	def klengthpref(self, arr, n, k, s):
		y = s[0:k]
		x = 0
		for i in arr:
			if y in i:
				x = x + 1
		return x