문제1306--섬 수

1306: 섬 수

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

R x C 격자 크기의 0과 1로 구성된 정보가 주어집니다. 여기서 0은 물을 나타내고, 1은 땅을 나타냅니다. 상하좌우로는 땅이 연결됩니다. 그러면 주어진 격자 정보에는 섬의 수를 찾아주세요. 주의. 대각선으로는 땅이 연결되어 있지 않습니다. 예를 들어 다음과 같이 2x2 정보가 주어지면,
1 0
0 1
두 땅은 서로 연결되어 있지 않으므로 섬의 수는 2입니다.

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=1,000)가 주어집니다. 각 테스트케이스의 첫 줄에는 R(1<=R<=300)과 C(1<=C<=300) 정보가 주어지며, 그다음 R줄에 격자 정보(각 줄에 C개의 0 또는 1)가 주어집니다. 

출력 설명

각 테스트케이스마다 섬의 수를 출력해 주세요.

입력 예시 Copy

4
4 5
1 1 1 1 0
1 1 0 1 1
1 1 0 0 0
0 0 0 0 0
3 3
0 0 0
0 1 0
0 0 0
2 2
0 1
1 0
1 1
0

출력 예시 Copy

1
1
2
0