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

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)
        
        
        

# cook your dish here
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

# cook your dish here
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))
# i am noob wanted to be better and trying hard for that
def printDivisors(n): 
    divisors=[]  
    # Note that this loop runs till square root 
    i = 1
    while i <= math.sqrt(n): 
          
        if (n % i == 0) : 
              
            # If divisors are equal, print only one 
            if (n//i == i) : 
                divisors.append(i) 
            else : 
                # Otherwise print both 
                divisors.extend((i,n//i)) 
        i = i + 1
    return divisors

def countTotalBits(num):
     
     # convert number into it's binary and 
     # remove first two characters 0b.
     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)

# cook your dish here
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)

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

# cook your dish here
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))

# cook your dish here
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))# cook your dish here


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)

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

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))
    
# cook your dish here