감자 수확

$r \times c$개의 정사각형 칸으로 나뉜 직사각형 밭이 있다.

밭의 모든 칸에서 감자가 자란다. 감자 수확기로 감자를 모두 수확하려고 한다. 감자 수확기는 기계 날개와 여러 장치를 갖춘 큰 차량이며, 땅속의 감자를 차 뒤쪽으로 옮긴다. 운전자는 날개를 켜고 끄는 스위치를 조작한다.

수확기는 이동 단위로 움직인다. 한 번의 이동에서는 밭의 한 행이나 한 열을 한쪽 끝에서 출발해 반대쪽 끝까지 지나간다. 수확기의 용량은 제한되어 있다. 한 번의 이동에서 수확할 수 있는 칸은 최대 $d$개이며, 그 칸들은 이동 경로에 있는 칸이면 어느 것이든 된다. 이 문제의 목표는 가장 적은 횟수의 이동으로 수확 일정을 만드는 것이다.

실제로는 한 가지 요소가 더 있다. 운전자는 복잡한 지시를 따르는 데 서툴다. 연속한 구간을 수확하는 편이 훨씬 간단하다. 적당한 위치마다 날개를 껐다 켜는 일은 번거롭다. 한 번의 이동에서 스위치를 누르는 횟수를 그 이동의 난이도로 본다. 즉 이동의 난이도는 그 이동에서 수확하는 연속 구간 수의 2배이다. 모든 칸은 정확히 한 번씩만 수확해야 한다. 이미 수확한 칸 위를 지나가면서 날개를 켜 두는 것은 허용되지 않는다. 땅이 상하기 때문이다.

일정의 난이도는 그 일정에 있는 이동들 가운데 가장 복잡한 이동의 난이도, 즉 이동별 난이도의 최댓값이다.

쉬운 데이터셋을 풀면서 난이도가 가장 작은 수확 일정을 하나 만들어라.

첫 줄에는 테스트 케이스의 개수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다. 각 테스트 케이스는 정수 $r$, $c$, $d$가 주어지는 한 줄이다.

각 테스트 케이스마다 $r$개의 행을 출력한다. 각 행에는 공백으로 구분된 양의 정수 $c$개가 있다. 각 정수는 그 칸을 수확하는 이동의 번호이다. 토큰의 개수만 맞으면 추가 공백은 허용된다.

$r, c \le 400$

첫 번째 테스트 케이스에서는 칸을 행 단위로 수확한다. 두 번째 테스트 케이스에서는 먼저 각 열에서 한 번씩 이동하고, 마지막 행에서 세 번 이동한다. 이 일정은 가장 짧지만 가능한 최소 난이도는 아니다. 이를 고치려면 8을 7 중 하나와 바꾸면 된다.