잔디깎이

Alice와 Bob의 집 앞에는 N미터 x M미터 크기의 직사각형 잔디밭이 있다. 매년 두 사람은 흥미로운 무늬로 잔디를 깎으려고 한다. 예전에는 전정가위로 잔디를 깎아서 시간이 매우 오래 걸렸지만, 이제 여러 설정을 지원하는 새로운 자동 잔디깎이가 생겨 이를 시험해 보려고 한다.

새 잔디깎이에는 높이 설정이 있다. 높이를 1밀리미터에서 100밀리미터 사이의 임의의 h로 설정할 수 있으며, 잔디깎이가 마주치는 h보다 높은 모든 잔디를 높이 h로 깎는다. 잔디밭 가장자리의 임의의 지점으로 잔디밭에 진입시켜 작동하면, 잔디깎이는 진입한 잔디밭 가장자리에 수직인 직선을 따라 반대편으로 빠져나갈 때까지 1m 너비의 띠에 있는 잔디를 깎는다. 잔디깎이의 높이는 잔디밭 위에 있지 않을 때만 설정할 수 있다.

Alice와 Bob에게는 잔디밭에 만들 수 있는 여러 잔디 무늬가 있다. 각 무늬에 대해 새 잔디깎이로 잔디를 그 무늬대로 깎을 수 있는지 알고 싶어 한다. 각 무늬는 잔디밭의 각 1m x 1m 정사각형에 있는 잔디의 높이를 지정하여 설명한다.

처음에는 잔디밭 전체의 잔디 높이가 100mm이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N, M ≤ 10. 1 ≤ $a_{i,j}$ ≤ 2.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N, M ≤ 100. 1 ≤ $a_{i,j}$ ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 M을 포함하는 한 줄로 시작한다. 다음 N개 줄에서 i번째 줄에는 M개의 정수 $a_{i,j}$가 각각 주어지며, 수 $a_{i,j}$는 i번째 행의 j번째 정사각형에서 원하는 잔디 높이를 나타낸다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 잔디깎이로 x번째 무늬를 만들 수 있으면 단어 "YES", 불가능하면 "NO"이다(따옴표는 명확성을 위해서만 사용했다).