There is a direct bidirectional road between every pair of distinct towns in the country. Peter wants to blow up enough of these roads that there are at least two towns that are no longer connected to each other by any direct or indirect paths.

You are given the cost of blowing up each road. Find the minimal total cost required for Peter to achieve their goal.

Input

Consists of multiple test cases. The first line of each test case contains the number n (n ≤ 50) of towns in a country. Next n lines describe the roads: the j-th character of the i-th line is a digit representing the cost of blowing up the road from the i-th town to the j-th town.

Output

For each test case print in a separate line the minimal total cost required for Peter to achieve their goal.