마법 사각형 분류

마술사 Matheos는 여러 정사각형 표를 그 마법적인 성질에 따라 분류하려고 한다. 여기서 사각형은 행의 수와 열의 수가 같은 정수 표이다. 각 사각형의 기준 합 S는 첫 번째 열에 있는 수들의 합으로 정한다.

사각형은 다음 규칙으로 분류한다.

• Not Magick: 하나 이상의 행 또는 열의 합이 S가 아니다.
• Semi-Magick Square: 모든 행과 모든 열의 합은 S이지만, 두 대각선 중 적어도 하나의 합이 S가 아니다.
• Weakly-Magick Square: 모든 행, 모든 열, 두 대각선의 합이 모두 S이다.
• Strongly-Magick Square: 모든 행, 모든 열, 두 대각선의 합이 모두 S이고, 표 안의 모든 수가 서로 다르다.
• Magically-Magick Square: 모든 행, 모든 열, 두 대각선의 합이 모두 S이고, 표 안의 모든 수가 서로 다르며, 그 수들이 빈틈없는 연속 정수이다.

다음 2 x 2 사각형은 모든 행과 열의 합이 5이지만 대각선의 합은 그렇지 않으므로 Semi-Magick Square이다.

다음 3 x 3 사각형은 모든 행, 열, 대각선의 합이 15이고, 모든 수가 서로 다르며, 1부터 9까지 연속하므로 Magically-Magick Square이다.

여러 사각형이 주어질 때, 각 사각형이 위 다섯 분류 중 어디에 속하는지 판정하는 프로그램을 작성하라.

입력은 여러 개의 사각형으로 이루어진다. 각 사각형은 한 줄에 정수 n이 먼저 주어지며, 이는 행과 열의 수를 뜻한다. 항상 2 <= n <= 8이다. 그다음 n개의 줄에 각각 n개의 정수가 주어진다. 입력은 0 하나만 있는 줄로 끝난다.

각 사각형마다 한 줄을 출력한다. 출력 형식은 Square k: result이며, k는 1부터 시작하는 사각형 번호이다. result에는 판정 결과에 따라 다음 문자열 중 하나를 정확히 출력한다.

• Magically-Magick Square
• Strongly-Magick Square
• Weakly-Magick Square
• Semi-Magick Square
• Not a Magick Square