from collections import deque
dx = [-1, 1, 0, 0] # 방향 벡터 차례대로 dx,dy인덱스 순으로 더해보면 상하좌우임을 알수있다.
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque([(x, y)]) # 큐 초기값 x와 y넣어줌(bfs 함수인자로 넘어온 x,y)
while queue:
x, y = queue.popleft() # 큐에서 하나를 빼고 x,y 변수에 그값들을 넣어줌
for i in range(4): # 상하좌우 위에 말한 방향 벡터순으로 돌림
nx, ny = x + dx[i], y + dy[i]
if nx >= N or nx < 0 or ny >= M or ny < 0 or arr[nx][ny] == 0: # 범위를 초과하거나 배추가 없는곳(0인 부분)을 제외시킴
continue
arr[nx][ny] = 0 # 탐색 했으니 방문했다라는 표시로 0으로 만듬 -> 앞으로 여기는 0이기 때문에 위에 써둔 조건때문에 앞으로 탐색하지 않음
queue.append((nx, ny)) # 이곳을 기준으로 다시 상하좌우를 봐야하기 때문에 큐에 넣어줌
# 여기선 직접 arr값을 변경시킴으로 방문을 했다라고 표시했지만 만약 bfs이후에도 arr이 쓸 곳이 있어서 변경되면 안되는 경우
# visited 리스트를 생성해서 visited = [[False for _ in range(M)] for _ in range(N)] visited[nx][ny] = True로 변경해가면서 처리하시면 됩니다
T = int(input()) # 테스트 케이스
for _ in range(T):
N, M, K = map(int, input().split()) # 원래는 M,N,K 순이지만 편의상 N,M을 바꿨음
arr = [[0 for _ in range(M)] for _ in range(N)] # 리스트 컴프리헨션 모르면 구글에 검색
ans = 0 # 답을 출력할 변수
for _ in range(K):
x, y = map(int, input().split())
arr[x][y] = 1 # 배추가 있는곳 1로 표시
for i in range(N):
for j in range(M):
if arr[i][j] == 1: # arr 2차원배열로 돌면서 배추가 있는곳은 bfs돌림
bfs(i, j)
ans += 1 # bfs가 끝났다면 상하좌우 인접한 배추들이 전부 탐색 됐을거고 이 한덩어리들이 배추흰지렁이들이 필요한 곳이기 때문에 1 더함
print(ans)
ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKCmR4ID0gWy0xLCAxLCAwLCAwXSAjIOuwqe2WpSDrsqHthLAg7LCo66GA64yA66GcIGR4LGR57J24642x7IqkIOyInOycvOuhnCDrjZTtlbTrs7TrqbQg7IOB7ZWY7KKM7Jqw7J6E7J2EIOyVjOyImOyeiOuLpC4KZHkgPSBbMCwgMCwgLTEsIDFdCgoKZGVmIGJmcyh4LCB5KToKICAgIHF1ZXVlID0gZGVxdWUoWyh4LCB5KV0pICMg7YGQIOy0iOq4sOqwkiB47JmAIHnrhKPslrTspIwoYmZzIO2VqOyImOyduOyekOuhnCDrhJjslrTsmKggeCx5KQogICAgd2hpbGUgcXVldWU6CiAgICAgICAgeCwgeSA9IHF1ZXVlLnBvcGxlZnQoKSAjIO2BkOyXkOyEnCDtlZjrgpjrpbwg67m86rOgIHgseSDrs4DsiJjsl5Ag6re46rCS65Ok7J2EIOuEo+yWtOykjAogICAgICAgIGZvciBpIGluIHJhbmdlKDQpOiAjIOyDge2VmOyijOyasCDsnITsl5Ag66eQ7ZWcIOuwqe2WpSDrsqHthLDsiJzsnLzroZwg64+M66a8CiAgICAgICAgICAgIG54LCBueSA9IHggKyBkeFtpXSwgeSArIGR5W2ldCiAgICAgICAgICAgIGlmIG54ID49IE4gb3IgbnggPCAwIG9yIG55ID49IE0gb3IgbnkgPCAwIG9yIGFycltueF1bbnldID09IDA6ICMg67KU7JyE66W8IOy0iOqzvO2VmOqxsOuCmCDrsLDstpTqsIAg7JeG64qU6rOzKDDsnbgg67aA67aEKeydhCDsoJzsmbjsi5ztgrQKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIGFycltueF1bbnldID0gMCAjIO2DkOyDiSDtlojsnLzri4gg67Cp66y47ZaI64uk652864qUIO2RnOyLnOuhnCAw7Jy866GcIOunjOuTrCAtPiDslZ7snLzroZwg7Jes6riw64qUIDDsnbTquLAg65WM66y47JeQIOychOyXkCDsjajrkZQg7KGw6rG065WM66y47JeQIOyVnuycvOuhnCDtg5Dsg4ntlZjsp4Ag7JWK7J2MCiAgICAgICAgICAgIHF1ZXVlLmFwcGVuZCgobngsIG55KSkgIyDsnbTqs7PsnYQg6riw7KSA7Jy866GcIOuLpOyLnCDsg4HtlZjsoozsmrDrpbwg67SQ7JW87ZWY6riwIOuVjOusuOyXkCDtgZDsl5Ag64Sj7Ja07KSMCgojIOyXrOq4sOyEoCDsp4HsoJEgYXJy6rCS7J2EIOuzgOqyveyLnO2CtOycvOuhnCDrsKnrrLjsnYQg7ZaI64uk65286rOgIO2RnOyLnO2WiOyngOunjCDrp4zslb0gYmZz7J207ZuE7JeQ64+EIGFycuydtCDsk7gg6rOz7J20IOyeiOyWtOyEnCDrs4Dqsr3rkJjrqbQg7JWI65CY64qUIOqyveyasAojIHZpc2l0ZWQg66as7Iqk7Yq466W8IOyDneyEse2VtOyEnCB2aXNpdGVkID0gW1tGYWxzZSBmb3IgXyBpbiByYW5nZShNKV0gZm9yIF8gaW4gcmFuZ2UoTildIHZpc2l0ZWRbbnhdW255XSA9IFRydWXroZwg67OA6rK97ZW06rCA66m07IScIOyymOumrO2VmOyLnOuptCDrkKnri4jri6QKCgoKVCA9IGludChpbnB1dCgpKSAjIO2FjOyKpO2KuCDsvIDsnbTsiqQKCmZvciBfIGluIHJhbmdlKFQpOgogICAgTiwgTSwgSyA9IG1hcChpbnQsIGlucHV0KCkuc3BsaXQoKSkgIyDsm5DrnpjripQgTSxOLEsg7Iic7J207KeA66eMIO2OuOydmOyDgSBOLE3snYQg67CU6r+o7J2MCiAgICBhcnIgPSBbWzAgZm9yIF8gaW4gcmFuZ2UoTSldIGZvciBfIGluIHJhbmdlKE4pXSAjIOumrOyKpO2KuCDsu7TtlITrpqztl6jshZgg66qo66W066m0IOq1rOq4gOyXkCDqsoDsg4kKICAgIGFucyA9IDAgIyDri7XsnYQg7Lac66Cl7ZWgIOuzgOyImAogICAgZm9yIF8gaW4gcmFuZ2UoSyk6CiAgICAgICAgeCwgeSA9IG1hcChpbnQsIGlucHV0KCkuc3BsaXQoKSkKICAgICAgICBhcnJbeF1beV0gPSAxICMg67Cw7LaU6rCAIOyeiOuKlOqzsyAx66GcIO2RnOyLnAogICAgZm9yIGkgaW4gcmFuZ2UoTik6IAogICAgICAgIGZvciBqIGluIHJhbmdlKE0pOgogICAgICAgICAgICBpZiBhcnJbaV1bal0gPT0gMTogIyBhcnIgMuywqOybkOuwsOyXtOuhnCDrj4zrqbTshJwg67Cw7LaU6rCAIOyeiOuKlOqzs+ydgCBiZnPrj4zrprwKICAgICAgICAgICAgICAgIGJmcyhpLCBqKQogICAgICAgICAgICAgICAgYW5zICs9IDEgIyBiZnPqsIAg64Gd64Ks64uk66m0IOyDge2VmOyijOyasCDsnbjsoJHtlZwg67Cw7LaU65Ok7J20IOyghOu2gCDtg5Dsg4kg65CQ7J2E6rGw6rOgIOydtCDtlZzrjanslrTrpqzrk6TsnbQg67Cw7LaU7Z2w7KeA66CB7J2065Ok7J20IO2VhOyalO2VnCDqs7PsnbTquLAg65WM66y47JeQIDEg642U7ZWoCiAgICBwcmludChhbnMpCg==