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

def maxmin():
    global bois,likes,n,boiscut
    maybest=[0]
    for x in range(n):
        for y in range(x+1,n):
            group=bois[x][:2]
            if bois[y][0] in group:
                group.remove(bois[y][0])
                aaaaa=[bois[y][1],group[0]]
                aaaaa.sort()
                if aaaaa in boiscut:
                    right=boiscut.index(aaaaa)
                    maybest.append(bois[x][2]+bois[y][2]+bois[right][2])
            elif bois[y][1] in group:
                group.remove(bois[y][1])
                aaaaa=[bois[y][0],group[0]]
                aaaaa.sort()
                if aaaaa in boiscut:
                    right=boiscut.index(aaaaa)
                    maybest.append(bois[x][2]+bois[y][2]+bois[right][2])
    return max(maybest)


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=maxmin()



    #Start
    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:
        firstbest = maxmin()

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

        print(max(firstbest,secondbest))
        
