테트로미노 최대 합

테트리스에 쓰이는 조각(테트로미노)은 정사각형 칸 네 개를 변끼리 이어 붙인 도형이며, 아래 5가지 종류가 있다.

I:  # # # #

O:  # #
    # #

T:  # # #
    . # .

S:  . # #
    # # .

L:  # .
    # .
    # #

정수로 채워진 $N \times N$ 크기의 표가 주어진다. 위 다섯 조각 중 하나를 표 위에 올려놓았을 때, 조각이 덮는 네 칸에 적힌 수의 합을 최대로 만드는 값을 구하여라.

각 조각은 90° 단위로 회전시킬 수 있으나 뒤집을(거울 대칭) 수는 없다. 회전을 고려하면 T와 L은 각각 4가지, I와 S는 각각 2가지, O는 1가지 형태를 가지므로 서로 다른 형태는 모두 13가지이다. 조각 전체가 표 안에 완전히 들어오는 배치만 유효하다.

예를 들어 I 조각을 가로로 놓으면 한 행에서 연속한 네 수의 합을, 90° 회전시켜 세로로 놓으면 한 열에서 연속한 네 수의 합을 얻는다. 표의 크기가 $4 \times 4$일 때 조각을 놓을 수 있는 서로 다른 위치는 모두 77가지이다.

조각은 반드시 하나 놓아야 하므로, 표의 모든 수가 음수이면 최대 합도 음수가 될 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에 표의 크기 $N$이 주어지며 $4 \le N \le 100$이다. 이어지는 $N$개의 줄에는 각 행에 해당하는 $N$개의 정수가 공백으로 구분되어 주어진다. 각 정수의 절댓값은 $1{,}000{,}000$ 이하이다.

입력의 마지막 줄에는 $0$이 하나 주어지며, 이는 입력의 끝을 나타낸다.

각 테스트 케이스마다 한 줄에 케이스 번호와 조각이 덮는 네 칸의 최대 합을 출력한다. 케이스 번호가 $k$, 최대 합이 $s$일 때 정확히 k. s 형식(번호, 마침표, 공백, 합)으로 출력하며, 케이스 번호는 $1$부터 시작한다.