L 모양 구획

$\mathbf{R}$개의 행과 $\mathbf{C}$개의 열로 이루어진 격자가 주어지며, 격자의 각 칸은 $0$ 또는 $1$이다.

선분은 모든 칸이 같은 행 또는 같은 열에 있는, 비어 있지 않은 연속한 칸들의 나열이다. 선분의 길이는 이 나열에 포함된 칸의 수로 정의한다.

선분의 모든 칸에 $1$만 들어 있으면 그 선분을 "good"라고 한다.

"L-shape"은 다음 속성을 모두 만족하는 순서 없는 선분 쌍으로 정의한다.

• 각 선분은 반드시 "good" 선분이어야 한다.

• 두 선분은 서로 수직이어야 한다.

• 두 선분은 양쪽 선분 모두의 끝점인 칸 하나를 공유해야 한다.

• 선분의 길이는 적어도 $2$이어야 한다.

• 더 긴 선분의 길이는 더 짧은 선분 길이의 두 배이다.

격자에 있는 L자 모양의 수를 세어야 한다.

아래에서 올바른 L자 모양의 예시 두 개를 볼 수 있다.

그리고 올바르지 않은 L자 모양의 예시 세 개가 있다.

왼쪽 모양에서는 두 선분이 공통 끝점을 공유하지 않는다는 점에 유의한다. 그다음 두 모양은 마지막 조건을 만족하지 않는다. 가운데 모양에서는 두 선분의 길이가 같고, 마지막 모양에서는 더 긴 선분이 더 짧은 선분 길이의 두 배보다 길다.

제한

시간 제한: 60초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 격자는 $0$과 $1$로만 이루어진다.

테스트 세트 1

$1 \le \mathbf{R} \le 40$. $1 \le \mathbf{C} \le 40$.

테스트 세트 2

최대 $5$개의 테스트 케이스에 대해 $1 \le \mathbf{R} \le 1000$ 및 $1 \le \mathbf{C} \le 1000$. 나머지 케이스에 대해서는 $1 \le \mathbf{R} \le 40$ 및 $1 \le \mathbf{C} \le 40$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $\mathbf{R}$와 $\mathbf{C}$가 주어진다.

이어서 $\mathbf{R}$개의 줄이 주어지며, 각 줄에는 격자의 칸을 나타내는 $\mathbf{C}$개의 정수가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$은 테스트 케이스 번호(1부터 시작)이고, $y$은 L자 모양의 수이다.

예제 케이스 #1에는 L자 모양이 하나 있다.

• 첫 번째 모양은 다음 칸들을 사용하여 만들어진다: $(1,1)$, $(2,1)$, $(3,1)$, $(4,1)$, $(4,2)$

예제 케이스 #2에는 L자 모양이 아홉 개 있다.

• 첫 번째 모양은 다음 칸들을 사용하여 만들어진다: $(1,1)$, $(2,1)$, $(3,1)$, $(4,1)$, $(5,1)$, $(6,1)$, $(6,2)$, $(6,3)$

• 두 번째 모양은 다음 칸들을 사용하여 만들어진다: $(3,1)$, $(4,1)$, $(5,1)$, $(6,1)$, $(6,2)$

• 세 번째 모양은 다음 칸들을 사용하여 만들어진다: $(6,1)$, $(5,1)$, $(4,1)$, $(3,1)$, $(3,2)$

• 네 번째 모양은 다음 칸들을 사용하여 만들어진다: $(3,3)$, $(4,3)$, $(5,3)$, $(6,3)$, $(6,2)$

• 다섯 번째 모양은 다음 칸들을 사용하여 만들어진다: $(6,3)$, $(5,3)$, $(4,3)$, $(3,3)$, $(3,2)$

• 여섯 번째 모양은 다음 칸들을 사용하여 만들어진다: $(3,1)$, $(3,2)$, $(3,3)$, $(3,4)$, $(2,4)$

• 일곱 번째 모양은 다음 칸들을 사용하여 만들어진다: $(3,4)$, $(3,3)$, $(3,2)$, $(3,1)$, $(2,1)$

• 여덟 번째 모양은 다음 칸들을 사용하여 만들어진다: $(3,4)$, $(3,3)$, $(3,2)$, $(3,1)$, $(4,1)$

• 아홉 번째 모양은 다음 칸들을 사용하여 만들어진다: $(6,3)$, $(5,3)$, $(4,3)$, $(3,3)$, $(3,4)$ 첫 세 개의 L자 모양은 아래 그림에 나와 있다.