GIven a 2d matrix , we need to find out how many rows and columns have sum between a given range(inclusive) in that matrix . All these ranges will be given in form of some queries.

Sample Input -> matrix - [[2,3],[5,9]], range queries - [[1,7],[6,14]]
Output - [2,3]

Explaination - for first range query i.e. [1,7] , we have first row(2+3=5) and first column(2+5=7) with sum between range. So output will be 2.
for second query i.e. [6,14] , we have first column(2+5=7), second column (3+9 = 12), second row(5+9=14), so output will be 3.

I could only think of a efficient approach, which is to precalculate prefix sum using given matrix and then for each query use binary search over the last column and last row for L and R then differences between the indexes of L and R will be count.

this way time complexity will be O(n**2) for precomputation, then O(q*logn).
where n = number of rows in matrix and q = number of given queries.

I need help with optimising this solution so that it pass test case because for now It is giving TLE for large input as number of queries are very large. Your suggestions are welcome.