Strongest Culture Interaction

In cultural studies, understanding how different cultures interact is crucial. You are given a matrix representing the interaction strengths between n cultures. The matrix is symmetric with zeros on its diagonal, which means that the interaction of a culture with itself is always 0. Your task is to determine the strongest interaction between any two distinct cultures for each test case.

Input Format: The input contains multiple test cases. Each test case starts with an integer \(n\) (the number of cultures) on a new line, followed by \(n\) lines, each containing \(n\) space-separated integers representing the strengths of interactions between cultures. The input ends with a line containing 0.

Output Format: For each test case, print a single integer on a new line representing the maximum interaction strength (considering only pairs \(i, j\) with \(i < j\)).

The formula for the solution can be represented as:

\( \text{result} = \max_{0 \le i < j < n} \{a_{ij}\} \)

inputFormat

Multiple test cases are given. Each test case begins with an integer n on a new line followed by n lines of space-separated integers. The sequence of test cases terminates with a single line containing 0.

outputFormat

For each test case, output a single integer on a new line which is the strongest interaction (i.e. the maximum value in the upper triangle of the matrix).## sample

4
0 2 3 4
2 0 5 1
3 5 0 7
4 1 7 0
0

7