Limits 1s, 512 MB

Most houses are not as safe as they could be. Earthquake engineering is an interdisciplinary branch of engineering that designs and analyzes structures, such as buildings and bridges, with earthquakes in mind. Its overall goal is to make such structures more resistant to earthquakes. US president Mr. Donald J. Trump wants to build a house for her wife. He owns a huge land where he wants to build the house. Unfortunately, the land is terrain and it has a variable elevation. It is shaped like a rectangle, N meters wide and M meters long. It can be divided into N·M squares (see the image). President’s house will be shaped like a rectangle that has sides parallel with the land’s edges and its vertices coincide with the vertices of the squares. All the land covered by President’s house must be of equal elevation to prevent it from collapsing in case of Earthquake.

So, you are hired to calculate the number of ways President can build his house for his beautiful wife! You might be rich after solving this problem for Mr. Trump.

Input

The first line of input gives the number of cases; TT (T200T ≤ 200). For each test case there will be two integers NN and MM (1N,M5001 ≤ N, M ≤ 500). Each of the following NN lines contains M integers aija_{ij} (1aij1000001 ≤ a_{ij} ≤ 100000), respectively the height of each square of land. After taking each input grid there will a new line.

Output

For each test case, output one line containing "Case t: " followed by the number of ways you can build President’s house.

Sample

InputOutput
3
2 3
1 1 2
1 1 1

3 3
3 5 3
5 3 3
5 5 5

5 3
3 3 3
3 3 7
7 7 7
3 7 3
7 3 7
Case 1: 13
Case 2: 15
Case 3: 27

Explanation of the third sample test case: Some of the possible house locations are rectangles with opposite vertices in (0,0)(1,1)(0,0)-(1,1), (0,0)(0,2)(0,0)-(0,2) (height 2) i (2,0)(2,2)(2,0)-(2,2), (1,2)(2,2)(1,2)-(2,2) (height 1). The first number in the brackets represents the row number & the second one the column number (0-indexed).


Submit

Login to submit.

Statistics

76% Solution Ratio
SeyedTabaEarliest, Jan '17
Ultra.NazmulFastest, 0.0s
seyedsszLightest, 131 kB
Ultra.NazmulShortest, 889B
Toph uses cookies. By continuing you agree to our Cookie Policy.