행렬 합

N행 M열로 이루어질 정수 행렬 A와 정수 x가 주어진다. 행렬 A의 모든 부분행렬 중 그 합이 x를 넘지 않는 (즉, x 이하인) 부분행렬의 개수를 구하고 싶다. 예를 들어 N = M = 2 이고 x = 5, 그리고 A가 아래와 같은 예를 생각해보자.

1 2
3 4

이 경우, 1x1 크기의 총 네 개의 부분행렬은 모두 그 원소의 합이 x = 5 이하이다. 1 과 3을 포함한 2x1 크기의 부분행렬과 1과 2를 포함한 1x2 크기의 부분행렬도 각각 원소의 합이 1+3 = 4 그리고 1+2 = 3으로 x 이하이므로 조건을 만족한다. 다른 부분행렬은 원소의 총 합이 5를 초과하므로, 이 경우 답은 6이 된다.

다른 예로, N = 2, M = 3, x = 0 이며 A가 아래와 같은 행렬인 경우를 생각해보자.

0 -1 -2
-3 -4 -5

이 경우, A의 모든 부분행렬의 원소 총 합이 0 이하이므로 답은 18이 된다.

N, M, x 그리고 A를 입력으로 받아, 원소의 총 합이 x이하인 부분행렬의 개수를 구하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 첫 줄에는 N, M, x 가 공백으로 구분되어 주어진다.

다음 N줄에 걸쳐 각 줄에 M개의 정수가 공백으로 구분되어 주어진다.

상기한대로 A의 부분행렬 중 원소의 총 합이 x이하인 부분행렬의 개수를 출력한다.

• 1 ≤ T ≤ 10
• -1,000,000,000 ≤ x ≤ 1,000,000,000 
• -100,000 ≤ A의 각 원소 ≤ 100,000