Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Earthquake!

By hasan169 · 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, T (≤ 200).
For each test case there will be two integers N and M (1 ≤ N, M ≤ 60). Each of the following N lines contains M integers aij (1 ≤ aij ≤ 100000), respectively the height of each square of land. After taking each input grid there will be 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. See the sample I/O.

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

Discussion

Statistics


87% Solution Ratio

SeyedTabaEarliest, Jan '17

Ultra.NazmulFastest, 0.0s

seyedsszLightest, 131 kB

Ultra.NazmulShortest, 889B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.