문제
어느 한 도시에서는 공장 단지가 부도가 나게 되어 넓은 공터가 경매에 올라오게 되었다. 이 공터는 가로와 세로 길이가 각각 인 정사각형 모양이며, 가로와 세로 길이가
인 정사각형 격자 모양으로 영역을 나누어 개별적으로 판매하고 있다.
그 도시에 살고있던 한 부자 경영인은 평소 자신이 기획해오던 놀이공원 건설 프로젝트를 몰래몰래 진행하기로 결정하였다. 때마침 경매에 올라온 이 공터에 관심을 가지게 된 경영인은 판매 중인 땅들 중 일부에 기존의 공장에서 배출된 폐기물들이 방치되어 있다는 사실을 알게 되었다. 놀이공원 건설을 위해서는 가로와 세로 길이가 인 정사각형 모양의 영역이 필요한데, 당연히 놀이공원 건설을 위해서는 해당 영역의 폐기물들을 모두 처리해야만 한다.
격자 모양의공터에서
크기의 땅을 구매하려고 할 때, 구매할 땅에 포함된 폐기물의 수를 최소화하는 영역을 찾는 프로그램을 작성하라.
예제 설명
첫 번째 예제에서 공원의 정보는 아래 그림과 같고, 크기의 영역을 선택해야 한다.
가운데 그림과 같이 파란색 영역을 선택하면 세 개의 폐기물을 처리해야 하지만, 오른쪽 그림과 같이 주황색 영역을 선택하면 한 개의 폐기물만 처리하면 된다.
다른 어떤 영역을 골라도 최소 한 개 이상의 폐기물을 처리해야 하므로, 답으로는 1을 출력해야 한다.
입력
첫째 줄에는 테스트 케이스의 개수 가 주어진다.
각 테스트 케이스의 입력은 아래와 같은 형식을 따른다.
첫째 줄에는 공터의 크기를 나타내는 과 구매할 땅의 크기를 나타내는
가 공백을 두고 주어진다.
다음 개의 줄에는 공터의 정보를 나타내는 정수가 한 줄에
개씩 공백을 두고 주어진다. 주어지는 정수는
또는
이며,
은 해당 칸이 비어있음을,
은 해당 칸에 폐기물이 있음을 의미한다.
- 입력에서 주어지는 수는 모두 정수이다.
출력
각 테스트 케이스에 대해, 모양의 땅을 구매했을 때 처리해야 하는 최소 폐기물의 수를 한 줄에 하나씩 출력한다.