블록 부수기

공중에 수평으로 매달린 $n \times m$ 크기의 직사각형 틀을 생각하자. 처음에 틀은 $1 \times 1$ 크기의 정사각형 블록 $n \times m$개로 빈틈없이 채워져 있다. 틀과 블록 사이, 그리고 블록끼리의 마찰 때문에 블록들은 안정적이며 떨어지지 않는다.

하지만 블록을 쳐서 떨어뜨릴 수 있다. 어떤 블록을 쳐서 떨어뜨리면, 남은 블록들이 주는 마찰만으로는 버티지 못하는 블록들이 함께 떨어질 수 있다. 정확히 말해, 블록이 맞거나 불안정하면 떨어진다. 블록은 왼쪽과 오른쪽 이웃 중 적어도 하나가 떨어졌고 앞뒤 이웃 중 적어도 하나도 떨어졌을 때 불안정하다. 이 정의에서 틀은 항상 안정적인 거대한 블록으로 볼 수 있다.

이제 블록 부수기인 당신은 블록을 쳐서 떨어뜨리려 한다. 정확히 말해, $q$번의 이동을 한다. $i$번째 이동에서 위치 $(x_i, y_i)$를 고른다. 고른 위치에 아직 블록이 있으면 그 블록을 쳐서 떨어뜨리고, 없으면 아무 일도 일어나지 않는다. 각 이동이 끝나면 불안정한 블록이 더 이상 떨어지지 않을 때까지 기다린 뒤 다음 이동을 한다.

예를 들어 다음 그림을 보자. 틀의 크기는 $2 \times 2$이고 블록 $(1, 1)$과 $(1, 2)$는 이미 떨어졌다. 여기서 블록 $(2, 2)$를 치면 이 블록이 떨어지고, 그 뒤 마지막으로 남은 블록 $(2, 1)$도 불안정해져 함께 떨어진다.

수행할 이동의 순서가 주어진다. 각 이동의 결과로 몇 개의 블록이 떨어지는지 구하자. 이동 중에 아무 일도 일어나지 않으면 그 이동의 답은 0이다.

첫째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 $T$가 주어진다. ($1 \le T \le 10$) 각 테스트 케이스는 다음과 같다.

첫째 줄에는 세 양의 정수 $n$, $m$, $q$가 주어진다. $n$과 $m$은 틀의 크기, $q$는 이동의 수다. ($1 \le n, m \le 2000$, $1 \le q \le 100\,000$)

다음 $q$개 줄에는 각각 두 양의 정수 $x_i$와 $y_i$가 주어지며, 다음에 수행할 이동을 나타낸다. ($1 \le x_i \le n$, $1 \le y_i \le m$)

각 테스트 케이스마다 $q$개 줄을 출력한다. 각 줄에는 해당 이동의 결과로 떨어지는 블록의 수를 나타내는 음이 아닌 정수를 출력한다.