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.

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.

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.

提交代码