satakshi-and-roses

As you all know, Valentine's day just passed. Here is a small incident from that day.

Mr. A wanted to ask her crush Satakshi out on a date.
Before that he wants to impress her.

For that, he has a rectangular shaped garden with N x M blocks. Each block has some number of roses in it.
All the roses in a block are united and hence cannot be separated.

Mr.A can impress her crush by selecting a sub-rectangle in the garden such that the total sum of number of roses in it is ≥ L and ≤ R. He will then gift this to her.
He needs your help in counting the number of ways to do that. Will you help him?

Input Format:

First line contains T, the number of test cases.
First line of each test case contains two integers N and M.
Second line contains two integers L and R.
Next N lines, each contains M integers, where A[i][j] = number of roses in corresponding block.

Output Format:

For each test case, print the number of ways to find a sub-rectangle in the garden such that number of roses in it ≥ L and ≤ R.

Constraints:

1 ≤ T ≤ 3

1 ≤ N , M ≤ 250

1 ≤ A[i][j] ≤ 100

1 ≤ L ≤ R ≤ N * M * max(A[i][j])

Author : Sumeet Varma

SAMPLE INPUT
2
1 3
2 3
1 2 1
3 3
2 6
1 4 2
2 3 4
1 2 3

SAMPLE OUTPUT
3
18

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: