提示: 欢迎访问OurACM平台。
Problem 1975 Link link look

Accept: 23    Submit: 272
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

“Link Link Look” is a very popular game, which you just need to use no more than three straight lines to eliminate two same patterns. It is showed in Figure 1.

Figure 1

The rule is simple, and the game is easy to play. Many people are addicted to cheat using “Wai Gua”. Tom would like to own one, but he is poor of algorithm, so he turns to you for help.

Given an n×n grid, indicating the map of “Link Link Look”. We use different positive integers to indicate different patterns. Zero indicates this grid is empty and a straight line can pass through it. If two same patterns are eliminated, a straight line can also pass through them. To simplify the problem, each pattern would appear at most twice. You should note that a straight line could not be outside of the map.

Please calculate the maximum number of patterns that can be eliminated.

Input

The first line is an integer T (T≤200), indicating the number of cases. Each case begins with a line containing an integer n (2≤n≤100), the size of “Link Link Look” is n×n. Each of the following n lines contains n nonnegative integers Gij (0≤Gij≤10,000, 1≤i≤N, 1≤j≤N) separated by a blank space, Gij denotes the status of the grid in row i and column j.

Output

For each test case, print a line containing the test case number (beginning with 1) and the maximum number of patterns that can be eliminated.

Sample Input

1 3 2 0 1 3 1 2 4 0 4

Sample Output

Case 1: 3

Source

The 35th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest

Submit  Back  Status  Discuss