안전한 정사각형

Codejamon 조련사들은 적극적으로 몬스터를 찾고 있지만, 조련사가 아니라면 이 몬스터들은 여러분에게 정말 위험할 수 있다. 몬스터가 하나도 없는 안전한 장소를 찾고 싶을 것이다!

우리의 세계를 격자로 생각하자. 일부 칸은 몬스터가 차지하고 있다. 몬스터를 하나도 포함하지 않는, 격자에 맞춰진 격자 칸들의 D × D 정사각형을 안전한 정사각형이라고 정의한다(단, D ≥ 1). 여러분의 임무는 세계 전체에 크기와 관계없이 안전한 정사각형이 몇 개 있는지 알아내는 것이다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB.

1 ≤ T ≤ 20.

각 i ≠ j에 대해 ($R_{i}$, $C_{i}$) ≠ ($R_{j}$, $C_{j}$)이다. (같은 격자 칸에 두 몬스터가 있는 경우는 없다.)

1부터 K까지의 i에 대해, 0 ≤ $R_{i}$ < R

1부터 K까지의 i에 대해, 0 ≤ $C_{i}$ < C

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

1 ≤ R ≤ 10.

1 ≤ C ≤ 10.

0 ≤ K ≤ 10.

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

1 ≤ R ≤ 3000.

1 ≤ C ≤ 3000.

0 ≤ K ≤ 3000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 R, C, K가 있는 한 줄로 시작한다. 격자는 R개의 행과 C개의 열로 이루어지며, K마리의 몬스터를 포함한다. 이어서 K개의 줄이 더 주어진다. 각 줄에는 두 정수 $R_{i}$와 $C_{i}$가 주어지며, i번째 몬스터가 있는 행과 열을 나타낸다. (행은 위에서 아래로 0부터 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 0부터 번호가 매겨진다.)

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 이 테스트 케이스의 안전 구역의 총개수이다.

예제 케이스 #1의 격자는 다음과 같다.

0 0 0 0 0 0 0 1 0

여기서 0은 몬스터가 없는 칸을 나타내고, 1은 몬스터가 있는 칸을 나타낸다. 이 격자에는 안전한 정사각형이 10개 있다. 8개의 1x1 정사각형과 2개의 2x2 정사각형이다.

예제 케이스 #2의 격자는 다음과 같다.

0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1

예제 케이스 #2은 큰 데이터 세트에만 등장한다. 이 격자에는 안전한 정사각형이 51개 있다. 32개의 1x1 정사각형, 13개의 2x2 정사각형, 5개의 3x3 정사각형, 그리고 1개의 4x4 정사각형이다.