It can be solve in O(n²) time per testcase if you something similar to two pointers instead of binary search. Let me explain:

At each position we try to increase the answer as much as possible (that is, as long as the 1 larger submatrix still has sum ≤ w). Now notice that the answer can only increase n times — so the whole thing is O(n²) (using prefix sums as you did).

Here's my AC code: link