Given N integers, the task is to insert those elements in the queue. Also, given M integers, the task is to find the frequency of each number in the Queue.
Note:
insert() will be called N times by main().
findFrequency() will be called M times by main();
Where k is each element passing through respective function calls.
Example 1:
Input:
N = 8
1 2 3 4 5 2 3 1
M = 5
1 3 2 9 10
Output:
2
2
2
-1
-1
Explanation:
After inserting 1, 2, 3, 4, 5, 2, 3 and 1 into the queue, frequency of 1 is 2, 3 is 2 and 2 is 2. Since 9 and 10 are not there in the queue we output -1 for them.
Example 2:
Input:
N = 6
1 2 1 1 1 4
M = 4
1 5 4 3
Output:
4
-1
1
-1
Explanation:
After inserting 1, 2, 1, 1, 1 and 4 into the queue, frequency of 1 is 4 and that of 4 is 1. Since 5 and 3 are not there in the queue we output -1 for them.
Your Task:
Your task is to complete the functions insert() and findFrequency() which inserts the element into the queue and find the count of occurences of element in the queue respectively.
Expected Time Complexity: O(N*M)
Expected Space Complexity: O(N)
Constraints:
1 <= N <= 10^{3}
1 <= M <= 10^{3}
1 <= Elements of Queue <= 10^{6}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3
class Solution:
    # Function to insert element into the queue
    def insert(self, q, k): 
        #code here
        
    # Function to find frequency of an element
    # return the frequency of k
    def findFrequency(self, q, k):
        # code here

Solutions:
class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		f = {}
		for i in q:
			if i not in f:
				f[i] = 1
			else:
				f[i] += 1
		for (i, j) in f.items():
			if i == k:
				return j
		return -1


class Solution:

	def insert(self, q, k):
		q.append(k)
		return q

	def findFrequency(self, q, k):
		d = dict()
		for ele in q:
			d[ele] = 0
		for ele in q:
			d[ele] = d[ele] + 1
		if k in d.keys():
			return d[ele]
		return -1


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		c = 0
		for i in q:
			if i == k:
				c += 1
		return c


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		return q.count(k)


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		count = 0
		que = []
		while len(q) != 0:
			popped = q.pop(0)
			que.append(popped)
			if popped == k:
				count += 1
		while len(que) != 0:
			popped = que.pop(0)
			q.append(popped)
		return count


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		count = 0
		dict = {}
		que = []
		while len(q) != 0:
			popped = q.pop(0)
			que.append(popped)
			if popped not in dict:
				dict[popped] = 1
			else:
				dict[popped] += 1
		while len(que) != 0:
			popped = que.pop(0)
			q.append(popped)
		if k in dict.keys():
			return dict[k]
		else:
			return 0


class Solution:

	def __init__(self):
		self.mp = {}

	def insert(self, q, k):
		q.append(k)
		self.mp[k] = self.mp.get(k, 0) + 1

	def findFrequency(self, q, k):
		if k not in q:
			return 0
		return self.mp[k]


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		if k in q:
			return q.count(k)
		else:
			return -1


class Solution:

	def insert(self, q, k):
		q.insert(0, k)

	def findFrequency(self, q, k):
		return q.count(k)


class Solution:

	def insert(self, q, k):
		q.append(k)
		return q

	def findFrequency(self, q, k):
		cnt = 0
		for ele in q:
			if ele == k:
				cnt += 1
		return cnt


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		kyu = set(q)
		for i in kyu:
			if k in kyu:
				return q.count(i)
			else:
				return -1


class Solution:

	def insert(self, q, k):
		q.append(k)
		return q

	def findFrequency(self, q, k):
		for i in q:
			return q.count(k)
		return -1


from collections import Counter

class Solution:

	def insert(self, q, k):
		q.append(k)
		return q

	def findFrequency(self, q, k):
		return q.count(k)


class Solution:

	def __init__(self):
		self.frecuency = {}

	def insert(self, q, k):
		q.append(k)
		if k in self.frecuency:
			self.frecuency[k] += 1
		else:
			self.frecuency[k] = 1

	def findFrequency(self, q, k):
		if k in self.frecuency:
			return self.frecuency[k]
		return -1


class Solution:

	def __init__(self):
		self.d = {}

	def insert(self, q, k):
		q.append(k)
		if k not in self.d:
			self.d[k] = 1
		else:
			self.d[k] += 1

	def findFrequency(self, q, k):
		if k in self.d:
			return self.d[k]
		return -1


class Solution:

	def insert(self, q, k):
		q.insert(0, k)

	def findFrequency(self, q, k):
		if k in q:
			return q.count(k)
		return -1


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		count = 0
		for i in range(len(q)):
			if q[i] == k:
				count += 1
		return count


from queue import Queue
import copy

class Solution:

	def __init__(self):
		self.queue = Queue()

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		return q.count(k)


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		freq = 0
		for x in q:
			if k == x:
				freq += 1
		return freq


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		l2 = []
		l2.append(k)
		for kk in l2:
			a = 0
			num = 0
			while a < n:
				if kk == q[a]:
					num = num + 1
				else:
					pass
				a = a + 1
			return num
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		obj = Solution()
		q = []
		n = int(input())
		arr = list(map(int, input().strip().split()))
		for k in arr:
			obj.insert(q, k)
		m = int(input())
		query = list(map(int, input().strip().split()))
		for k in query:
			f = obj.findFrequency(q, k)
			if f != 0:
				print(f)
			else:
				print(-1)


class Solution:

	def __init__(self):
		self.dic = {}

	def insert(self, q, k):
		q.append(k)
		if k in self.dic:
			self.dic[k] += 1
		else:
			self.dic[k] = 1

	def findFrequency(self, q, k):
		if k in self.dic:
			return self.dic[k]
		else:
			return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		obj = Solution()
		q = []
		n = int(input())
		arr = list(map(int, input().strip().split()))
		for k in arr:
			obj.insert(q, k)
		m = int(input())
		query = list(map(int, input().strip().split()))
		for k in query:
			f = obj.findFrequency(q, k)
			if f != 0:
				print(f)
			else:
				print(-1)


from collections import deque

class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		dl = deque(q)
		return dl.count(k)


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		a = q.count(k)
		if a > 0:
			return a
		return -1


from collections import defaultdict

class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		temp = q
		mp = defaultdict(lambda : 0)
		for i in q:
			mp[i] += 1
		return mp[k]


class Solution:

	def __init__(self):
		self.mp = dict()

	def insert(self, q, x):
		q.append(x)
		if x in self.mp:
			self.mp[x] += 1
		else:
			self.mp[x] = 1

	def findFrequency(self, q, k):
		if k not in self.mp:
			return -1
		return self.mp[k]


class Solution:

	def __init__(self):
		self.hash = {}

	def insert(self, q, k):
		q.append(k)
		self.hash[k] = self.hash.get(k, 0) + 1

	def findFrequency(self, q, k):
		if k in self.hash:
			return self.hash[k]
		else:
			return -1


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		i = 0
		cnt = 0
		while i < len(q):
			if k == q[0]:
				cnt += 1
			q.append(q.pop(0))
			i += 1
		return cnt


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		queue = []
		c = 0
		while q:
			x = q.pop()
			if x == k:
				c += 1
			queue.append(x)
		while queue:
			q.append(queue.pop(0))
		return c


class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		count = 0
		q2 = []
		while len(q):
			element = q.pop(0)
			if k == element:
				count += 1
			q2.append(element)
		while len(q2):
			q.append(q2.pop(0))
		if count == 0:
			return -1
		else:
			return count


class Solution:

	def insert(self, q, k):
		q.append(k)
		return q

	def findFrequency(self, q, k):
		_dict = {}
		for qi in q:
			if qi not in _dict:
				_dict[qi] = 1
			else:
				_dict[qi] += 1
		if k in _dict.keys():
			return _dict[k]
		else:
			return -1


import collections

class Solution:

	def insert(self, q, k):
		q.append(k)

	def findFrequency(self, q, k):
		c = collections.Counter(q)
		return c[k]


import collections

class Solution:

	def insert(self, q, k):
		q.append(k)
		return q

	def findFrequency(self, q, k):
		z = q.count(k)
		return z