선발 명단

챔피언스 리그 결승을 앞둔 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 쓰려고 한다.

결승에 나설 선발 선수 11명은 이미 골랐지만, 어느 선수를 어느 포지션에 세울지는 아직 정하지 못했다.

수석코치 마이크 펠란은 11명의 선수가 각 포지션에서 발휘할 능력을 0부터 100까지의 정수로 수치화했다. $0$은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.

11개의 포지션에 모두 선수를 한 명씩 배치하되, 어떤 선수도 능력치가 $0$인 포지션에는 세울 수 없다. 이때 배치된 선수들의 능력치 합이 최대가 되도록 하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 $C$가 주어진다. 각 케이스는 11줄로 이루어지며, $i$번째 줄에는 $0$ 이상 $100$ 이하의 정수 11개 $s_{ij}$가 주어진다. $s_{ij}$는 $i$번 선수가 $j$번 포지션에서 뛸 때의 능력치이다. 모든 선수에 대해, 능력치가 $0$보다 큰 포지션(즉 적합한 포지션)의 수는 최대 5개이다.

각 테스트 케이스마다, 11개의 포지션을 모두 채웠을 때 얻을 수 있는 능력치 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 올바른 라인업을 하나 이상 만들 수 있다.