In a multi-storied building, there are some families who know each other very well. They like to have a lot of fun, so they often want to get together in one of those apartments to have a party. To understand the uniqueness of this group, let us consider a co-ordinate system where (x, y, z) denotes the co-ordinate of an apartment. Here, z axis denotes the floor of the apartment and (x, y) co-ordinates form the plane parallel to the land. Now there is an interesting fact: there are no two families in their group such that their apartments have the same (x,y) co-ordinate. Moreover, for every possible value of (x,y), the there exists exactly one apartment in which one of these families live. Therefore, we can represent the floor of each of their apartments in a table as the following figure: Here, you can consider the rows of the table parallel to x-axis and columns of the tables parallel to y-axis of the building. So, if the cell of 1st row and 1st column denotes 6, that means one of their friends live in the apartment on 6th floor of the building with co-ordinate (1, 1). It is not always possible for each family to be present in every party, but whenever a subset of these families gets together for a party, they have to satisfy the following properties: • This subset is formed by a rectangle (axis-parallel) drawn on the table. • The party will be held in one of the apartments of this subset (Obviously). • The summation of floors they need to go up or down must be minimized. If there are multiple floors which satisfy this requirement, they will always choose the higher floor. • After selecting the apartment, if it is on a floor lower than h, the party will be cancelled. For example, say the families marked in grey (in the table shown above) want to hold a party and h=3. Both4thand5thfloorhasthesamesummationoffloorstheyneedtogoupordown(2+1+ 11 = 14 for 4th floor and 3 + 1 + 10 = 14 for 5th floor). As they always prefer the higher floor, it will be held on the 5th floor. As it is not lower than 3rd floor (h = 3), it also satisfies the last requirement. You need to write a program to determine the the largest number of families who can get together for a party satisfying all those requirements. Input The first line will contain the number of test cases, T (1 ≤ T ≤ 20). Each test case starts with a line containing two integers, R (1 ≤ R ≤ 250) and C (1 ≤ C ≤ 250) denoting the number of rows and columns in the table, respectively. Then R lines follow, each containing C integers denoting the floors of corresponding apartments. Then there will be a line containing a single integer, Q (1 ≤ Q ≤ 10) which denotes the number of queries to follow. Then the following line contains Q integers, where each one denotes the value of h. All integers in the input file will be positive and in the range of 32-bit signed integer. Output For each case, print a line containing ‘Case < x >:’ where x is the case number. Then the follow- ing Q lines should contain one integer: the largest number of families who can get together for the corresponding value of h.
2/2 Sample Input 1 34 6 10 3 1 5425 1 7 4 15 2 65 Sample Output Case 1: 6 12