33485번 - 진한이의 지뢰찾기 서브태스크스페셜 저지

2025년 2월 8일, <제6회 MatKor Cup:2025 Winter>가 지금까지 열렸던 대회 중 최대 규모로 개최된다. 동우, 재우, 종우, 재현이를 비롯한 많은 MatKor Cup 임원진 및 운영진이 이번 대회를 끝으로 졸업하거나 군대를 가기 때문에 이번 대회부터는 AlKor와 공동 주최를 하기로 했다.

진한이는 자신만 계속 남아 있다는 사실에 화가 난다. 그래서 진한이는 $N\times M$ 크기의 격자판에 지뢰를 배치하려고 한다.

격자판의 각 칸은 .(빈칸) 또는 #(지뢰)로 이루어져 있으며, 배치는 다음 조건을 만족해야 한다.

• 모든 .로 표시된 칸은 상, 하, 좌, 우로 인접한 칸 중 적어도 하나가 #이어야 한다.

지뢰는 비싸기 때문에 진한이는 가능한 적은 수의 지뢰를 사용하려고 한다. 진한이를 위해 조건을 만족하는 배치 중 지뢰 개수가 가장 적은 배치를 찾아 출력하자.

첫 번째 줄에 테스트 케이스의 개수 $T(1\leq T\le 1\,000)$가 주어진다.

각 테스트케이스의 첫 번째 줄에 두 정수 $N(1\le N\le 1\,000)$, $M(1\le M\le 1\,000)$이 공백으로 구분되어 주어진다.

모든 테스트 케이스에서 $N\times M$의 합은 $10^6$를 넘지 않는다.

각 테스트 케이스에 대해 첫 번째 줄에 사용한 지뢰의 개수를 출력한다. 이후 $N$개의 줄에 걸쳐 조건을 만족하는 배치를 출력한다.

조건을 만족하는 배치가 여러 개 존재할 수 있으며, 그중 하나를 출력하면 된다.