Cliques

Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

In graph theory, we call a subgraph of a undirected graph clique if each pair of nodes in it owns an edge between them. Consider a undirected graph G with n nodes. We hope to modify G into a new graph such that each connected component of it should be a clique. Each step of modification can be inserting a new edge or deleting an edge which has already existed.

Input

The first line of the input contains an integer t which is the number of test cases. For each test case, the first line consists of an integer n (1 ≤ n ≤ 100) which is the number of nodes in undirected graph G. Each of the following n lines consists of n integers corresponding to the adjacency matrix of G where 1 represents the existence of the edge and 0 otherwise.

Output

For each test case, output first the case number, see the sample output. There should be a space after the colon in each test case. Then, if the graph G can be modified into a new graph with no more than ten steps, output the minimum number of steps we need, or - 1 if not.

Sample Input

2 7 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0

Sample Output

Case #1: 2 Case #2: 0

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区青岛站-重现赛(感谢中国石油大学)

提交代码