In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
We are given a grid consisting of unit squares. Each of the unit squares contains a single integer. In this task we are interested in arithmetic rectangles lying on the grid, i.e., rectangles composed of unit squares such that numbers in every row and every column form arithmetic sequences. Recall that an arithmetic sequence is a sequence in which any two consecutive terms differ by the same amount.
In addition, we aim to find the largest arithmetic rectangle, i.e., the one covering the most unit squares. For example, the largest arithmetic rectangle on the grid below consists of nine unit squares:
In the first line of the input there is a single integer () denoting the number of test cases that follow. The description of each test case begins with a line with two integers and (). In each of the following lines there are integers from the range . These numbers describe the grid. The size of each input file will not exceed 20 MB.
Your program should output lines with answers for the consecutive test cases. The answer for a single test case is one integer equal to the number of unit squares contained in the largest arithmetic rectangle that can be found on the grid described in the test case.
For the input data:
2 4 4 5 3 5 7 2 4 4 4 3 5 3 1 6 3 2 4 2 3 0 1 2 1 2 3
the correct result is:
Task author: Jakub Radoszewski.