Raj loves to listen to songs in his free time. It’s his birthday tomorrow and his friend Neelansh wants his gift to be the most unique. Being great at making music, he decides to produce a song for him. However, Raj likes songs according to their beauty. He determines the beauty of the song as the number of times all the octave musical tones are completed in ascending order.

He begins with a jumbled tone of length N and numbers each octave tone as 1,2,3….8.

Neelansh wants to maximize the beauty of the song but since he uses the trial version of the software,
- He cannot change the size of N.
- He cannot introduce any new tone, but can choose any two tones and swap their positions

However, Neelansh just received a mail that he needs to submit all his pending assignments by tomorrow. He has tons of assignments left to do, but he doesn’t want to spoil the idea of his gift. Can you help him? 

-----INPUT-----
- The first line contains a single integer T- the number of test cases  
- The first line of each test case contains a single integer N- the length of the song  
- The second line contains N- space separated integers ai,  ai+1,.....aN 

-----OUTPUT-----
For each test case, print a single line containing one integer- the maximum possible beauty of the song  

-----CONSTRAINTS-----
1<=T<=102
1<=N<=105
1<=a<=8

-----EXAMPLE INPUT-----
2

8

1 2 3 4 5 6 7 8

16

1 2 1 2 3 3 4 4 5 5 6 6 7 8 7 8

-----EXAMPLE OUTPUT-----
1

2

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	d = {}
	for ele in ar:
		if ele in d:
			d[ele] += 1
		else:
			d[ele] = 1
	m = 99999
	count = 0
	for ele in d:
		count += 1
		if m > d[ele]:
			m = d[ele]
	if count != 8:
		print(0)
	else:
		print(m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dic = {}
	for i in range(1, 9):
		dic[i] = a.count(i)
	ans = min(dic.values())
	print(ans)


try:
	for _ in range(int(input())):
		n = input()
		arr = list(map(int, input().split()))
		s = [1, 2, 3, 4, 5, 6, 7, 8]
		mini = 100000
		for x in s:
			coun = arr.count(x)
			if coun < mini:
				mini = coun
		print(mini)
except:
	pass


from collections import Counter
import string
import math
import sys

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return list(map(int, sys.stdin.readline().split()))

def makedict(var):
	return dict(Counter(var))

def printDivisors(n):
	divisors = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				divisors.append(i)
			else:
				divisors.extend((i, n // i))
		i = i + 1
	return divisors

def countTotalBits(num):
	binary = bin(num)[2:]
	return len(binary)
for _ in range(vary(1)):
	n = vary(1)
	num = array_int()
	nt = makedict(num)
	st = set((1, 2, 3, 4, 5, 6, 7, 8))
	for i in nt:
		if i in st:
			st.remove(i)
	if len(st) != 0:
		print(0)
	else:
		mini = float('inf')
		for i in nt:
			if nt[i] < mini:
				mini = nt[i]
		print(mini)


T = int(input())
for case in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	time = []
	for i in range(1, 9):
		time.append(a.count(i))
	print(min(time))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0 for x in range(11)]
	for i in a:
		b[i] += 1
	ans = b[1]
	for i in range(1, 9):
		ans = min(ans, b[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr_c = [arr.count(i) for i in range(1, 9)]
	print(min(arr_c))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0}
	for i in l:
		d[i] += 1
	print(min(d.values()))


for j in range(int(input())):
	n = int(input())
	nums = input().strip()
	octave = []
	for i in set(nums):
		octave.append(nums.count(i))
	octave.sort()
	if len(set(nums)) == 9:
		print(octave[0])
	else:
		print(0)


try:
	for z in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		z = max(a)
		b = []
		for i in range(z):
			b.append(a.count(i + 1))
		print(min(b))
except:
	pass


t = int(input())
for test in range(t):
	n = int(input())
	mydict = {}
	arr = list(map(int, input().strip().split()))
	minimum = 9999999
	for i in range(1, 9):
		mydict[i] = arr.count(i)
		if mydict[i] < minimum:
			minimum = mydict[i]
	print(minimum)


for _ in range(int(input())):
	(n, val) = (int(input()), list(map(int, input().split())))
	total_ct = 0
	counts = []
	for i in range(1, 9):
		counts.append(val.count(i))
	total_ct = min(counts)
	print(total_ct)


T = int(input())
for _ in range(T):
	N = int(input())
	a = sorted(list(map(int, input().split())))
	count = 0
	b = []
	for i in range(1, 9):
		b.append(a.count(i))
	print(min(b))


n = int(input())
for _ in range(n):
	l = int(input())
	t = map(int, input().split())
	accumm = [0] * 8
	for i in t:
		accumm[i - 1] += 1
	print(min(accumm))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	cnt = Counter()
	l = list(map(int, input().split()))
	for i in l:
		cnt[i] += 1
	if len(cnt.keys()) == 8:
		print(min(set(cnt.values())))
	else:
		print(0)


for i in range(int(input())):
	x = int(input())
	s = list(input())
	ans = []
	for j in range(1, 9):
		ans.append(s.count(str(j)))
	print(min(ans))


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	res = [0] * 8
	for i in range(8):
		res[i] = arr.count(i + 1)
	print(min(res))


t = int(input())
while t:
	n = int(input())
	notes = [int(x) for x in input().split()]
	count = []
	for i in range(1, 9):
		count.append(notes.count(i))
	print(min(count))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	nums = [0, 0, 0, 0, 0, 0, 0, 0]
	for i in a:
		nums[i - 1] += 1
	if min(nums) == 0:
		print(0)
	else:
		print(min(nums))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {i: 0 for i in range(1, 9)}
	for i in a:
		d[i] = d[i] + 1
	print(min(d.values()))


for _ in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	for i in s:
		try:
			d[i] += 1
		except:
			d[i] = 1
	ans = 1000000000
	for i in range(1, 9):
		x = str(i)
		try:
			ans = min(ans, d[x])
		except:
			ans = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(c) for c in input().split()]
	t = [0 for i in range(8)]
	for i in l:
		t[i - 1] += 1
	print(min(t))