You are given a dataset consisting of $N$ items. Each item is a pair of a word and a boolean denoting whether the given word is a spam word or not.
We want to use this dataset for training our latest machine learning model. Thus we want to choose some subset of this dataset as training dataset. We want to make sure that there are no contradictions in our training set, i.e. there shouldn't be a word included in the training set that's marked both as spam and not-spam. For example item {"fck", 1}, and item {"fck, 0"} can't be present in the training set, because first item says the word "fck" is a spam, whereas the second item says it is not, which is a contradiction.
Your task is to select the maximum number of items in the training set.
Note that same pair of {word, bool} can appear multiple times in input. The training set can also contain the same pair multiple times.

-----Input-----
- First line will contain $T$, number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains a string $w_i$, followed by a space and an integer(boolean) $s_i$, denoting the $i$-th item.

-----Output-----
For each test case, output an integer corresponding to the maximum number of items that can be included in the training set in a single line.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 25,000$
- $1 \le |w_i| \le 5$ for each valid $i$
- $0 \le s_i \le 1$ for each valid $i$
- $w_1, w_2, \ldots, w_N$ contain only lowercase English letters

-----Example Input-----
3
3
abc 0
abc 1
efg 1
7
fck 1
fck 0
fck 1
body 0
body 0
body 0
ram 0
5
vv 1
vv 0
vv 0
vv 1
vv 1

-----Example Output-----
2
6
3

-----Explanation-----
Example case 1: You can include either of the first and the second item, but not both. The third item can also be taken. This way the training set can contain at the very max 2 items.
Example case 2: You can include all the items except the second item in the training set.

Difficulty: interview

Starter code:

Solutions:
t = int(input())

for _ in range(t):
    n = int(input())
    
    a = {}
    
    for i in range(n):
        l = input()
        
        if l not in a:
            a[l] = 1
        else:
            a[l] += 1
    
    done = []
    ans = 0
    
    for i in a:
        if a[i] != 0:
            temp = [x for x in i.split()]
            v = temp[0]
            
            v0 = v + " 0"
            v1 = v + " 1"
            
            if(v0 in a and v1 in a):
                if a[v0] > a[v1]:
                    ans += a[v0]
                else:
                    ans += a[v1]
            
                a[v0] = a[v1] = 0
            elif(v0 in a):
                ans += a[v0]
                a[v0] = 0
            elif(v1 in a):
                ans += a[v1]
                a[v1] = 0
    
    print(ans)

t=int(input())
ans=[]
for i in range(t):
    count=0
    d=dict()
    n=int(input())
    count=0
    for j in range(n):
        x,y=input().split()
        y=int(y)
        if(x not in d):
            d[x]=[0,0]
        d[x][y]+=1
    for i in d:
        count+=max(d[i])
    ans.append(count)
for i in ans:
    print(i)

t=int(input())
ans=[]
for i in range(t):
    count=0
    d=dict()
    n=int(input())
    count=0
    for j in range(n):
        x,y=input().split()
        y=int(y)
        if(x not in d):
            d[x]=[0,0]
        d[x][y]+=1
    for i in d:
        count+=max(d[i])
    ans.append(count)
for i in ans:
    print(i)

t=int(input())
ans=[]
for i in range(t):
    count=0
    d=dict()
    n=int(input())
    count=0
    for j in range(n):
        x,y=input().split()
        y=int(y)
        if(x not in d):
            d[x]=[0,0]
        d[x][y]+=1
    for i in d:
        count+=max(d[i])
    ans.append(count)
for i in ans:
    print(i)

from collections import OrderedDict

for i in range(int(input())):
    N = int(input())
    dic = OrderedDict()
    for i in range(N):
        n, m = list(input().split())
        if n in dic :
            if m=='1':
                dic[n][1]+=1
            else :
                dic[n][0]+=1
        else :
            if m=='1':
                dic[n] = [0,1]
            else :
                dic[n]=[1,0]
    count = 0
    for k,v in dic.items():
        count+= max(v[0],v[1])
    print(count)

# cook your dish here
from collections import defaultdict
for _ in range(int(input())):
    mp = defaultdict(lambda:0)
    sat = set()
    for _ in range(int(input())):
        w,s = input().split()
        mp[w,s]+=1
        sat.add(w)
    ans = 0
    for i in sat:
        ans += max(mp[i,'0'],mp[i,'1'])
    print(ans)
        
        

#by nikkipinky
for _ in range(int(input())):
    n=int(input())
    countPairs=dict()
    for i in range(n):
        word,spam=input().split()
        spam=int(spam)
        if(word not in countPairs):
            countPairs[word]=[0,0]
        countPairs[word][spam]+=1
    finalcount=0
    for i in countPairs:
        finalcount+=max(countPairs[i])
    print(finalcount)

for _ in range(int(input())):
    d = dict()
    count = 0
    for i in range(int(input())):
        ip = input().split()
        if ip[0] in d:
            if int(ip[1]) == 1:
                d[ip[0]][1] += 1
            else:
                d[ip[0]][0] += 1
        else:
            if int(ip[1]) == 1:
                d.update({
                    ip[0]: {0: 0, 1: 1}
                })
            else:
                d.update({
                    ip[0]: {0: 1, 1: 0}
                })
    for j in d.values():
        count += max(j.values())
    print(count)

# cook your dish here
T = int(input())
for i in range(T):
    n=int(input())
    d=dict()
    for i in range(n):
        x,y=input().split()
        y=int(y)
        if x not in d:
            d[x]=[0,0]
        d[x][y]+=1
    res=0
    for i in d:
        res+=max(d[i])
    print(res)

# cook your dish here
for _ in range(int(input())):
    n=int(input())
    d=dict()
    for i in range(n):
        x,y=input().split()
        y=int(y)
        if x not in d:
            d[x]=[0,0]
        d[x][y]+=1
    ans=0
    for i in d:
        ans+=max(d[i])
    
        
    print(ans)
        

t=int(input())
for T in range(0,t):
    n=int(input())
    dict0 = {}
    dict1 = {}
    total = 0
    listset = set()
    for i in range(0,n):
        a,b=map(str,input().split())
        listset.add(a)
        if b == '0':
            if a in dict0 :
                dict0[a] += 1
            else:
                dict0[a] = 1
        else:
            if a in dict1 :
                dict1[a] += 1
            else:
                dict1[a] = 1

    for j in listset:
        if j in dict0 and j in dict1:
            if dict0[j]<dict1[j]:
                total += dict1[j]
            else:
                total += dict0[j]
        elif j in dict0:
            total += dict0[j]
        else:
            total += dict1[j]
    print(total)

T=int(input())
for q in range(T):
    n=int(input())
    d=dict()
    for i in range(n):
        x,y=input().split()
        y=int(y)
        if x not in d:
            d[x]=[0,0]
        d[x][y]+=1
    tot=0
    for j in d:
        tot+=max(d[j])
    print(tot)

# cook your dish here
try:
    t=int(input())
    while(t>0):
        t-=1
        n=int(input())
        check={}
        sm=0
        for i in range(n):
            st,bl=input().split(' ')
            if st in check:
                if bl=='0':
                    check[st][0]+=1
                else:
                    check[st][1]+=1
            else:
                if bl=='0':
                    check[st]=[1,0]
                else:
                    check[st]=[0,1]
        for i in check:
            sm=sm+max(check[i])
        print(sm)
except EOFError:
    pass

# cook your dish here
try:
    t=int(input())
    while(t>0):
        t-=1
        n=int(input())
        check={}
        sm=0
        for i in range(n):
            st,bl=input().split(' ')
            if st in check:
                if bl=='0':
                    check[st][0]+=1
                else:
                    check[st][1]+=1
            else:
                if bl=='0':
                    check[st]=[1,0]
                else:
                    check[st]=[0,1]
        for i in check:
            sm=sm+max(check[i])
        print(sm)
except EOFError:
    pass

try:
    t=int(input())
    while(t>0):
        t-=1
        n=int(input())
        check={}
        sm=0
        for i in range(n):
            st,bl=input().split(' ')
            if st in check:
                if bl=='0':
                    check[st][0]+=1
                else:
                    check[st][1]+=1
            else:
                if bl=='0':
                    check[st]=[1,0]
                else:
                    check[st]=[0,1]
        for i in check:
            sm=sm+max(check[i])
        print(sm)
except EOFError:
    pass
    


for _ in range(int(input())):
    n = int(input())
    D = dict()
    for i in range(n):
        word,tp = map(str,input().split())
        tp = int(tp)
        
        if tp==1:
            if D.get(word,0)!=0 : D[word][0]+=1
            else : D[word] = [1,0]
        else : 
            if D.get(word,0)!=0 : D[word][1]+=1
            else : D[word] = [0,1]
    max_select = 0
    for a,b in D.values():
        max_select+=max(a,b)
    print(max_select)
        

# cook your dish here
for _ in range(int(input())):
    N = int(input())
    A= {}
    for i in range(N):
        w, s = input().split()
        s = int(s)
        if w not in A:
            A[w] = [1,0] if s == 0 else [0,1]
        else:
            if s == 0:
                A[w][0] += 1 
            else:
                A[w][1] += 1 
    c = 0
    for i in A.values():
        c += max(i)
    print(c)


t = int(input())
for _ in range(t):
    n = int(input())
    d = {}
    l = []
    count = 0
    for i in range(n):
        a,b = input().split()
        l.append(a)
        if (a,b) not in d:
            d[(a,b)] = 0
        d[(a,b)] += 1
    l = set(l)
    for i in l:
        count += d.get((i,'0'),0) if d.get((i,'0'),0) > d.get((i,'1'),0) else d.get((i,'1'),0)
    print(count)
        
        

# cook your dish here
for _ in range(int(input())):
    N = int(input())
    S = {}
    for i in range(N):
        w, s = input().split()
        s = int(s)
        if w not in S:
            S[w] = [1,0] if s == 0 else [0,1]
        else:
            if s == 0:
                S[w][0] += 1 
            else:
                S[w][1] += 1 
    c = 0
    for i in S.values():
        c += max(i)
    print(c)

for _ in range(int(input())):
    n=int(input())
    k={}
    for i in range(n):
        a,b=map(str,input().split())
        b=int(b)
        if a not in k:
            s=[0,0]
            if b==0:
                s[0]=1
            else:
                s[1]=1
            k[a]=s
        else:
            if b==0:
                k[a][0]+=1
            else:
                k[a][1]+=1
    c=0            
    for i in k.values():
        c+=max(i)
    print(c)    
        
                

# cook your dish here
import math
t=int(input())
#t=1
#res=[]
for i in range(t):
    n=int(input())
    #n,q=map(int,input().split())
    #l=list(map(int,input().split()))
    l={}
    for j in range(n):
        w,s=input().split()
        s=int(s)
        if w not in l:
            l[w]=[1,0] if s==0 else [0,1]
        else:
            if s==0:
                l[w][0]+=1
            else:
                l[w][1]+=1
    c=0
    for i in l.values():
        c+=max(i)
    print(c)

    

for _ in range(int(input())):
    N = int(input())
    S = {}
    for i in range(N):
        w, s = input().split()
        s = int(s)
        if w not in S:
            S[w] = [1,0] if s == 0 else [0,1]
        else:
            if s == 0:
                S[w][0] += 1 
            else:
                S[w][1] += 1 
    c = 0
    for i in S.values():
        c += max(i)
    print(c)


for _ in range(int(input())):
    N = int(input())
    S = {}
    for i in range(N):
        w, s = input().split()
        s = int(s)
        if w not in S:
            S[w] = [1,0] if s == 0 else [0,1]
        else:
            if s == 0:
                S[w][0] += 1 
            else:
                S[w][1] += 1 
    c = 0
    for i in S.values():
        c += max(i)
    print(c)

t=int(input())
for i in range(t):
    n=int(input())
    c=0
    dict1=dict()
    dict2=dict()
    for i in range(n):
        w,s1=input().split()
        s=0
        s=int(s1)
        if(s==0):
            if(w not in dict2):
                dict2[w]=1
            elif(w in dict2):
                dict2[w]+=1
        if(s==1):
            if(w not in dict1):
                dict1[w]=1
            elif(w in dict1):
                dict1[w]+=1
    for i in dict1:
        if(i not in dict2):
            c+=dict1[i]
        elif(i in dict2):
            c+=max(dict1[i],dict2[i])
    for i in dict2:
        if(i not in dict1):
            c+=dict2[i]
    print(c)
        
            
    
        


t = int(input())
for asdf in range(t):
    n = int(input())
    dic = {}
    for sdfd in range(n):
        inp = input()
        split = inp.split(" ")
        if not split[0] in dic: 
            if int(split[1])==1:
                dic[split[0]] = [0, 1]
            else:
                dic[split[0]] = [1, 0]
        else:
            if int(split[1])==1:
                dic[split[0]][1] += 1
            else:
                dic[split[0]][0] += 1
    
    total = 0
    for x in dic:
        if dic[x][0]>= dic[x][1]:
            total += dic[x][0]
        else:
            total += dic[x][1]
    print(total)