미니 스도쿠 X

미니 스도쿠 X는 6 × 6 격자를 숫자로 채우는 퍼즐이다. 다음 그룹이 모두 1부터 6까지의 숫자를 각각 정확히 한 번씩 담으면 그 격자는 올바른 답이다.

• 6개 행 각각
• 6개 열 각각
• 왼쪽 위 칸에서 오른쪽 아래 칸으로 이어지는 대각선
• 오른쪽 위 칸에서 왼쪽 아래 칸으로 이어지는 대각선
• 2행 3열 크기의 블록 6개. 1행과 2행, 3행과 4행, 5행과 6행을 각각 1열부터 3열까지 또는 4열부터 6열까지와 맞춘 영역이다.

아래 격자는 올바른 답이고, 두 대각선에 놓인 칸을 회색으로 칠했다.

숫자 36개로 이루어진 격자를 읽어 올바른 답인지 판정하는 프로그램을 작성하라.

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수 $T$가 주어진다 ($T \le 100000$). 다음 줄부터 테스트 케이스가 차례로 주어진다.

테스트 케이스는 각각 여섯 줄이고, 한 줄에는 공백으로 구분된 한 자리 정수 여섯 개가 있다. 한 자리 정수이므로 1에서 6 사이가 아닌 숫자도 올 수 있으며, 그런 숫자가 있는 격자는 올바른 답이 아니다.

각 테스트 케이스마다 Case#x: M 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, M은 그 테스트 케이스가 올바른 답이면 1, 아니면 0이다. Case와 # 사이에는 공백이 없다.