import sys
t = int(sys.stdin.readline())

def minmax():
    global likes,bois
    female=-1
    bestamount=0
    for girl in range(1,len(likes)):
        for pair in likes[girl]:
            totalamount=bois[pair[0]][2]+bois[pair[1]][2]
            if totalamount>bestamount:
                female=girl
                bestamount=totalamount
                bestpair=pair
    if female!=-1:
        return [female,bestamount,bestpair]
    else:
        return -1

for _ in range(t):
    n = int(sys.stdin.readline())
    bois=[]
    likes=[[] for _ in range(2*n+1)]
    likesnotpair=[[] for _ in range(2*n+1)]
    for x in range(n):
        inpt=list(map(int, sys.stdin.readline().split()))
        bois.append(inpt)
        likesnotpair[inpt[0]].append(x)
        likesnotpair[inpt[1]].append(x)


    for x in range(n):
        group=bois[x][:2]
        for y in range(x+1,n):
            if bois[y][0] in group:
                likes[bois[y][0]].append([x,y])
            elif bois[y][1] in group:
                likes[bois[y][1]].append([x,y])
    
    
    res = minmax()
    
    boiscut=[]
    for x in bois:
        boiscut.append(x[:2])
    
    if res==-1:
        fin=0
        for x in bois:
            if fin < x[2]:
                fin=x[2]
        print(fin)
    else:
        bla=boiscut[res[2][0]].copy()
        bla.remove(res[0])
        bla=bla[0]
        ble=boiscut[res[2][1]].copy()
        ble.remove(res[0])
        ble=ble[0]

        others=[bla,ble]
        others.sort()

        rest1=0
        if others in boiscut:
            rest1=bois[boiscut.index(others)][2]
        

        #secondbest
        secondbest=[]
        for x in likesnotpair:
            girlfans=0
            for boy in x:
                girlfans+=bois[boy][2]
            secondbest.append(girlfans)
        secondbest=max(secondbest)



        likesnotpair[res[0]].remove(res[2][0])
        likesnotpair[res[0]].remove(res[2][1])
        rest2=0
        for x in likesnotpair[res[0]]:
            rest2+=bois[x][2]

        
        firstbest=res[1]+max(rest1,rest2)

        print(max(firstbest,secondbest))
        
