Chef is making Window frames for his new office, for this he has  n wooden Logs whose lengths are l1, l2, … ln respectively. Chef Doesn’t want to break any logs or Stick 2 or more logs together.
To make a  h × w Window Frame, he needs two Logs with lengths equal h and two with length . 
The Chef wants as much sunlight in as possible and for it he has decided to make from the available logs as many frames as possible. Help him in finding the number of window Frames that he can make. 
Note : Chef do not need to use all the logs
Input:
The first line of the input contains a single integer T denoting the number of test cases. The description of each test case follows :.
The first line of each test case contains a single integer n the number of wooden logs. 
The second line contains  n space-separated integers l1,l2,l3….ln The length of each wooden log
Output: 
The only line in Output Contains single Integer denoting the maximum possible number of Wooden Frames.
Constraints:
1 ≤ T ≤ 10
1 ≤ n ≤ 100
1 ≤ li ≤ 10000
Example Input:
2
4
1 2 1 2
8
1 2 1 3 4 1 5 6
Example Output:
1
0
Explanation :
First Case :  We can build a frame of dimension 1x2 as two logs of each dimension are available.
Second Case :  We can’t build any Frame as no logs of length except 1 have more than one piece.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
t=int(input())
j=0
while j<t:
    n=int(input())
    lst=list(map(int,input().split()))
    s=set()
    d=list()
    for i in lst:
        if i in s:
            s.remove(i)
            d.append(i)
        else:
            s.add(i)
    x=len(d)
    if x%2==0:
        print(x//2)
    else:
        print((x-1)//2)
    j+=1

test = int(input())

for t in range(test):
  n = int(input())
  mark = [0 for i in range(10001)]
  
  logs = list(map(int, input().strip().split()))
  use = []
  
  for log in logs:
    mark[log] += 1
    
    if mark[log]>=2:
      use.append(log)
      
  use = list(set(use))
  #print(use)
  
  #make windows
  full = 0
  half = 0
  
  for log in use:
    full += (mark[log]//4)
    mark[log] = mark[log]%4
    half += (mark[log]//2)
    
  print(full+(half//2))

# cook your dish here
for o in range(int(input())):
	n = int(input())
	a = list(map(int ,input().split()))
	dic = {}
	s = 0
	for i in a:
		dic[i] = dic.get(i,0) +1
	for i in dic.values():
		if i >=2:
			s = s+i
	print(s//4)

import collections
def solve(n,l):
    c=0
    d=collections.Counter(l)
    for i in d:
        if d[i]>=2:
            c+=d[i]//2
    return c//2     
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    print(solve(n,l))


# cook your dish here
t=int(input())
for i in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    s=set(l)
    d=[]
    d1=[]
    h=0
    for j in s:
        d.append(l.count(j))
    d2=list(set(d))
    d2.sort(reverse=True)
    for v in d2:
        if (v>1) and (v%2==0):
            d1.append(v)
    for k in d1:
        q=k//2
        if (d.count(k)==2):
            h=h+q
        elif q>=2:
            h=h+(q//2)
            
    if h==0: 
        print(0)
    else:
        print(h)
        
        
    
        
        
        


# cook your dish here
t=int(input())
for i in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    s=set(l)
    d=[]
    d1=[]
    h=0
    for j in s:
        d.append(l.count(j))
    d2=list(set(d))
    d2.sort(reverse=True)
    for v in d2:
        if (v>1) and (v%2==0):
            d1.append(v)
    for k in d1:
        q=k//2
        if (d.count(k)==2):
            h=h+q
        elif q>=2:
            h=h+(q//2)
            
    if h==0: 
        print(0)
    else:
        print(h)
        
        
    
        
        
        


# cook your dish here
t = int(input())

for _ in range(t):
    n = int(input())
    arr = list(map( int, str(input()).split() ))
    
    visited = set()
    doubles = []
    for i in arr:
        if i in visited:
            visited.remove(i)
            doubles.append(i)
        else:
            visited.add(i)
    print(len(doubles)//2)


t=int(input())
while(t>0):
    n=int(input())
    a=list(map(int,input().split()))
    c=0
    for i in a:
        d=a.count(i)
        for j in range(1,d):
            a.remove(i)
        if(d>=2):
            c+=d//2
    print(c//2)        
    t-=1

# cook your dish here
a=int(input())
for i in range(a):
    t=int(input())
    l=list(map(int,input().split()))
    l2=[]
    for j in l:
        if j not in l2:
            l2.append(j)
    l3=[]
    for k in l2:
        l3.append(l.count(k))
    c=0
    for j in l3:
        c1=j
        if c1>=2:
            while(c1>=2):
                c+=1
                c1=c1-2
    print(round(c/2))


for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    t=[0]*(10001)
    for i in l:
        t[i]+=1
    s=0
    for j in t:
        s+=j//2
    print(s//2)

t=int(input())
for i in range(t):
    n=int(input())
    lst1=list(map(int,input().split()))
    lst2=[]
    for j in lst1:
        if j not in lst2:
            lst2.append(j)
    lst3=[]
    for k in lst2:
        lst3.append(lst1.count(k))
    c1=0
    for j in lst3:
        c=j
        if c>=2:
            while(c>=2):
                c1+=1
                c=c-2
    print(round(c1/2))
#cook your dish here