투도쿠

톰(Tom)은 여러 수학 분야에 정통한 연구자로, 대학에 연구실을 세우고 짐(Jim) 같은 신입생을 가르친다. 첫 수업에서 톰은 짐에게 투도쿠(Tudoku) 라는 게임을 소개했다. 투도쿠는 스도쿠(Sudoku)의 간단한 변형으로, 거의 모든 칸이 이미 채워져 있는 보드에서 시작한다. 이것은 톰이 평범한 스도쿠를 풀다가 마지막 몇 칸을 채우기 귀찮아 그만두었을 때 남는 보드다. 톰이 짐에게 남긴 모든 투도쿠를 풀 수 있도록 도와주자.

스도쿠는 9 × 9 보드에서 진행되며, 보드는 아홉 개의 3 × 3 블록으로 나뉜다. 처음에는 일부 칸에만 숫자가 있고, 목표는 각 행, 각 열, 각 3 × 3 블록에 1부터 9까지의 숫자가 정확히 한 번씩 들어가도록 나머지 칸을 채우는 것이다.

모든 투도쿠 보드는 다음 규칙을 반복 적용하면 반드시 풀 수 있다: 어떤 행, 열, 또는 3 × 3 블록에 숫자가 정확히 여덟 개 채워져 있다면 그 안의 빈 칸 하나는 유일하게 정해지므로 그 숫자를 채운다. 이 규칙을 반복하면 입력의 모든 보드를 끝까지 채울 수 있음이 보장된다.

첫 번째 줄에 시나리오의 개수가 주어진다. 각 시나리오는 아홉 개의 숫자로 이루어진 아홉 개의 줄로 구성된다. 값이 0인 칸은 톰이 아직 채우지 않아 여러분이 채워야 하는 칸을 뜻한다. 각 시나리오 뒤에는 빈 줄이 하나 온다.

각 시나리오에 대해 먼저 Scenario #i: 형식의 줄을 출력한다. 여기서 i는 1부터 시작하는 시나리오 번호이다. 그다음 완성된 투도쿠 보드를 입력과 같은 형식으로, 즉 0이 있던 자리를 올바른 숫자로 바꾸어 아홉 개의 줄로 출력한다. 각 시나리오의 출력은 빈 줄로 마무리한다.