1607: Cable Donation

A local charity is asking for donations of Ethernet cable. You realize that you probably have a lot of extra cable in your house, and make the decision that you will donate as much cable as you can spare.
You will be given several lines of characters indicating the length (in meters) of cables between each pair of rooms in your house. You wish to keep only enough cable so that every pair of rooms in your house is connected by some chain of cables, of any length. The jth character of line i gives the length of the cable between rooms i and j in your house. A value of ‘0‘ (zero) indicates no cable, values of ‘a‘ through ‘z‘ indicate lengths of 1 through 26, and values of ‘A‘ through ‘Z‘ indicate lengths of 27 through 52.
If both the jth character of line i and the ith character of line j are greater than 0, this means that you have two cables connecting rooms i and j, and you can certainly donate at least one of them. If the ith character of line i is greater than 0, this indicates unused cable in room i, which you can donate without affecting your home network in any way.
You are not to rearrange any cables in your house; you are only to remove unnecessary ones. Output the maximum total length of cables (in meters) that you can donate. If any pair of rooms is not initially connected by some path, output -1.

The input will contain several test cases. The first line in the input contains the number of test cases N. For each test case: The first line contains one integer M (1 ≤ M ≤ 50), indicating the number of rooms. This is followed by M lines describing length of cables between each pair of rooms in your house.

For each test case, output one integer on a separate line, which is the maximum total length of cables (in meters) that you can donate.

5
3
abc
def
ghi
2
a0
0b
4
0X00
00Y0
0000
00Z0
2
Az
aZ
4
0top
c0od
er0o
pen0

40
-1
0
105
134