스도쿠 검사기

스도쿠는 인기 있는 일인용 게임이다. 목표는 각 열, 각 행, 그리고 서로 겹치지 않는 9개의 3x3 부분 행렬 모두가 1부터 9까지의 모든 숫자를 포함하도록 9x9 행렬을 숫자로 채우는 것이다. 각 9x9 행렬은 게임을 시작할 때 일부가 채워져 있으며, 일반적으로 해가 유일하다.

완성된 $N^{2}$ $xN^{2}$ 스도쿠 행렬이 주어질 때, 유효한 해인지 판정하는 것이 목표이다. 유효한 해는 다음 조건을 만족해야 한다.

• 각 행은 1부터 $N^{2}$까지의 각 수를 정확히 한 번씩 포함한다.

• 각 열은 1부터 $N^{2}$까지의 각 수를 정확히 한 번씩 포함한다.

• $N^{2}$ $xN^{2}$ 행렬을 서로 겹치지 않는 $N^{2}$개의 NxN 부분 행렬로 나눈다. 각 부분 행렬은 1부터 $N^{2}$까지의 각 수를 정확히 한 번씩 포함한다.

문제의 해가 유일한지는 고려할 필요가 없다. 주어진 행렬이 유효한 해인지 확인하기만 하면 된다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

1 ≤ T ≤ 100.

테스트 세트 1 - 공개

N = 3.

테스트 세트 2 - 비공개

3 ≤ N ≤ 6.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N으로 시작한다. 다음 $N^{2}$개의 줄은 완성된 스도쿠 해를 나타내며, 각 줄에는 정확히 $N^{2}$개의 정수가 주어진다. 입력으로 주어지는 모든 정수는 양수이며 1000보다 작다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, 유효한 해라면 y는 "Yes", 유효하지 않다면 "No"이다(따옴표는 명확성을 위해서만 표시했다). 채점기는 대소문자를 구분하므로 "yes"와 "no"는 정답으로 인정되지 않는다는 점에 유의한다.