Very Important Persons
면접 대비시간 제한2초메모리 제한512 MB
n행 m열 좌석에 손님 번호 1부터 nm을 배치하며 (1,1)에는 nm을 두고, 시장 좌석과의 맨해튼 거리가 멀수록 번호가 작아지게 한다.
문제
N국립대학교의 새 캠퍼스 개교식에 nm명의 귀빈이 방문한다. 개교식은 직사각형 모양의 강당에서 열리며, 강당의 좌석은 n개의 행에 배치되고 각 행에는 m개의 좌석이 있다. 행은 1부터 n까지 번호가 매겨지고, 각 행의 좌석은 1부터 m까지 번호가 매겨지며, i번째 행의 j번째 좌석을 (i, j)로 나타낸다.
개교식 주최측은 손님들에게 중요도에 따라 1부터 nm까지 번호를 매겼다. 번호가 클수록 더 중요한 손님이다. 가장 중요한 손님인 시장은 nm번을 받는다. 시장은 (1, 1) 좌석에 앉을 계획이다. 이제 나머지 손님들에게 좌석을 배정해야 한다. 손님들은 중요도에 따라 배치되어야 하며, 번호가 큰 손님이 번호가 작은 손님보다 시장으로부터 더 멀리 앉는 상황이 있어서는 안 된다. 두 좌석 (r1, s1)과 (r2, s2) 사이의 거리는 |r1 - r2| + |s1 - s2|로 측정한다.
주최측이 손님들에게 좌석을 배정하도록 도와라.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 수 t (1 ≤ t ≤ 400)가 주어진다.
각 테스트 케이스는 두 개의 정수 n과 m (1 ≤ n, m ≤ 20)을 포함하는 한 줄로 주어진다.
출력
각 테스트 케이스마다 손님들에게 좌석을 배정한 후의 강당 배치도를 출력한다.
n개의 줄을 출력하며, 각 줄에는 m개의 정수가 있어야 하고, i번째 줄의 j번째 정수는 좌석 (i, j)에 배정될 손님의 중요도와 같아야 한다.
좌석을 손님들에게 배정하는 유효한 방법이 여러 가지라면, 그중 아무거나 출력한다.