Sumdoku

Sumdoku는 스도쿠의 변형이다. 스도쿠처럼 $9 \times 9$ 격자를 1부터 9까지의 숫자로 채우되, 각 숫자가 모든 행에 정확히 한 번, 모든 열에 정확히 한 번, 9개의 $3 \times 3$ 작은 사각형 각각에 정확히 한 번 나와야 한다. 스도쿠는 몇몇 칸의 값을 미리 고정하지만, Sumdoku는 같은 $3 \times 3$ 사각형 안에서 맞닿은 두 칸의 합에 조건을 건다.

두 칸 사이에 놓인 기호 <, =, >는 그 양쪽 두 값의 합이 각각 10보다 작다, 10과 같다, 10보다 크다는 뜻이다. 가로로 맞닿은 쌍이면 왼쪽과 오른쪽 값의 합이고, 세로로 맞닿은 쌍이면 위와 아래 값의 합이다. 조건은 같은 사각형 안에서 맞닿은 칸 쌍에만 붙고, 사각형 경계를 넘는 쌍에는 붙지 않는다.

아래 그림은 기호가 격자에 놓이는 방식을 보여 준다.

조건이 주어지면 격자를 채워라.

첫 줄에 데이터 집합의 개수 $P$가 주어진다 ($1 \le P \le 500$). 데이터 집합은 서로 독립이고 똑같은 방식으로 처리한다.

데이터 집합 하나는 16줄이다. 첫 줄에는 데이터 집합 번호 $K$가 있고, $K$는 1부터 $P$까지 순서대로 증가한다. 이어지는 15줄은 문자 <, =, >로만 이루어진다.

1, 3, 5, 6, 8, 10, 11, 13, 15번째 줄은 각각 6글자이고, 순서대로 격자 1행부터 9행까지 가로로 맞닿은 칸 쌍의 조건이다. 한 줄의 6글자는 열 쌍 (1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9)의 조건이다.

2, 4, 7, 9, 12, 14번째 줄은 각각 9글자이고, 순서대로 행 쌍 (1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9)에서 세로로 맞닿은 칸 쌍의 조건이다. 한 줄의 9글자는 1열부터 9열까지의 조건이다.

모든 데이터 집합에는 조건을 만족하는 격자가 적어도 하나 있다.

데이터 집합마다 10줄을 출력한다. 첫 줄에는 데이터 집합 번호 $K$를 출력하고, 이어지는 9줄에는 격자의 각 행을 출력한다. 그 9줄 중 $i$번째 줄의 $j$번째 수는 $i$행 $j$열의 값이고, 한 줄의 아홉 수는 공백 한 칸으로 구분한다.

조건을 만족하는 격자가 여럿이면, 81개의 값을 1행 1열부터 행 우선 순서로 읽었을 때 사전순으로 가장 앞서는 격자를 출력한다.