행렬 합

N행 M열 정수 행렬 A와 정수 x가 주어진다. A의 부분행렬 중 원소의 합이 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