Starting Lineup

Ahead of a Champions League final, Manchester United's celebrated manager Ferguson wants to use a 4-4-2 diamond formation.

The 11 starters for the final have already been chosen, but it is not yet decided which player goes to which position.

Assistant coach Mike Phelan rated each of the 11 players' ability in each position as an integer from 0 to 100. A $0$ means the player is not suited to that position.

Assign exactly one player to each of the 11 positions so that every position is filled and no player is placed in a position where their ability is $0$. Write a program that makes this assignment so that the total ability of the placed players is as large as possible.

The input consists of several test cases. The first line contains the number of test cases $C$. Each case consists of 11 lines; the $i$-th line contains 11 integers $s_{ij}$ between $0$ and $100$, where $s_{ij}$ is player $i$'s ability in position $j$. For every player, the number of positions with ability greater than $0$ (its suitable positions) is at most 5.

For each test case, output on its own line the maximum total ability achievable when all 11 positions are filled. At least one valid lineup always exists.