L자 모양 도형

R개의 행과 C개의 열로 이루어진 격자가 있고, 각 칸은 0 또는 1이다.

선분은 같은 행이나 같은 열에 연속으로 놓인 비어 있지 않은 칸들의 나열이다. 선분의 길이는 그 나열에 속한 칸의 개수로 정의한다.

선분에 속한 모든 칸이 1이면 그 선분을 "좋은" 선분이라고 한다.

"L자 모양"은 다음 조건을 모두 만족하는 두 선분의 순서 없는 쌍으로 정의한다.

• 두 선분은 각각 "좋은" 선분이어야 한다.
• 두 선분은 서로 수직이어야 한다.
• 두 선분은 양쪽 모두의 끝점인 칸 하나를 공유해야 한다.
• 두 선분의 길이는 각각 2 이상이어야 한다.
• 긴 선분의 길이는 짧은 선분의 길이의 두 배여야 한다.

격자에 있는 L자 모양의 개수를 구하시오.

아래는 올바른 L자 모양 두 가지 예시이다.

그리고 아래는 잘못된 L자 모양 세 가지 예시이다.

왼쪽 도형에서는 두 선분이 공통 끝점을 공유하지 않는다. 가운데 도형은 두 선분의 길이가 같고, 오른쪽 도형은 긴 선분이 짧은 선분의 두 배보다 길어서 둘 다 마지막 조건을 만족하지 않는다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그 뒤에 T개의 테스트 케이스가 이어진다.

각 테스트 케이스의 첫 줄에는 두 정수 R과 C가 주어진다.

그다음 R개의 줄에 걸쳐 각 줄에 C개의 정수가 주어지며, 격자의 칸을 나타낸다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 L자 모양의 개수이다.

• 1 ≤ T ≤ 100.
• 격자는 0과 1로만 이루어진다.

샘플 케이스 1에는 L자 모양이 하나 있다.

• 첫 번째 L자 모양은 (1,1), (2,1), (3,1), (4,1), (4,2) 칸으로 이루어진다.

샘플 케이스 2에는 L자 모양이 아홉 개 있다.

• 첫 번째 L자 모양은 (1,1), (2,1), (3,1), (4,1), (5,1), (6,1), (6,2), (6,3) 칸으로 이루어진다.
• 두 번째 L자 모양은 (3,1), (4,1), (5,1), (6,1), (6,2) 칸으로 이루어진다.
• 세 번째 L자 모양은 (6,1), (5,1), (4,1), (3,1), (3,2) 칸으로 이루어진다.
• 네 번째 L자 모양은 (3,3), (4,3), (5,3), (6,3), (6,2) 칸으로 이루어진다.
• 다섯 번째 L자 모양은 (6,3), (5,3), (4,3), (3,3), (3,2) 칸으로 이루어진다.
• 여섯 번째 L자 모양은 (3,1), (3,2), (3,3), (3,4), (2,4) 칸으로 이루어진다.
• 일곱 번째 L자 모양은 (3,4), (3,3), (3,2), (3,1), (2,1) 칸으로 이루어진다.
• 여덟 번째 L자 모양은 (3,4), (3,3), (3,2), (3,1), (4,1) 칸으로 이루어진다.
• 아홉 번째 L자 모양은 (6,3), (5,3), (4,3), (3,3), (3,4) 칸으로 이루어진다.

처음 세 L자 모양은 아래 그림에 나와 있다.