Save the nature

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
The new king of Byteland, John2318, has just ascended the throne. As every new king, he wants to build a spectacular palace to showcase his wealth and power.
We can consider Byteland as an N x M rectangular matrix A. If A[i][j] is positive, then it means that A[i][j] litres of oxygen are produced by trees in the cell with coordinates (i, j) every day. On the other hand, a negative value of A[i][j] indicates that a Byteland resident lives in this cell, who consumes A[i][j] litres of oxygen every day.
The palace will occupy some rectangle submatrix of A. All the cells within the palace premises will not produce nor consume any oxygen.
Byteland scientists discovered the new important fact: if Byteland will be producing S less litres of oxygen every day than it produces now, it will lead to a natural disaster. So now everyone is interested in the following question: how many ways exist for choosing a rectangular region for the planned palace?
Input
The first line contains one integer T denoting the number of testcases.
Each testcase starts with a line containing three spaceseparated integers N, M, and S. The following N lines contain M integers each and describe the cells of the matrix A.
Output
For each testcase, output a single line containing one integer  the number of rectangles where the palace can be built without causing a disaster.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N, M ≤ 150
 10^{9} ≤ A[i][j] ≤ 10^{9}
 1 ≤ S ≤ 10^{9}
Subtasks
 Subtask 1 (27 points) 1 ≤ N, M ≤ 20, time limit = 1 sec
 Subtask 2 (30 points) 1 ≤ N, M ≤ 50, time limit = 1 sec
 Subtask 3 (43 points) 1 ≤ N, M ≤ 150, time limit = 3 sec
Example
Input: 2 2 3 7 1 2 3 4 5 6 3 3 12 3 3 3 4 4 4 3 3 3 Output: 11 27
Explanation
Test case 1: we have the following matrix A:
1 2 3
4 5 6
There are 11 rectangular submatrices with sum ≤ S = 7: all the 6 cells themselves, 2 columns (the left and the middle), 1 row (the first), and 2 segments in the first row of length 2 each.
Author:  pavel1996 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/SVNTR 
Tags  fenwick, ltime29, medium, mergesort, pavel1996 
Date Added:  26092015 
Time Limit:  1  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 