You are given a complete undirected graph. For each pair of vertices you are given the length of the edge that connects them. Find the shortest paths between each pair of vertices in the graph and return the length of the longest of them.

Input

The first line of the input contains a single integer N (3 ≤ N ≤ 10).

The following N lines each contain N space-separated integers. jth integer in ith line aij is the length of the edge that connects vertices i and j. aij = aji, aii = 0, 1 ≤ aij ≤ 100 for i ≠ j.

Output

Output the maximum length of the shortest path between any pair of vertices in the graph.

Examples

Input

3
0 1 1
1 0 4
1 4 0


Output

2


Input

4
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0


Output

5

Note

You're running short of keywords, so you can't use some of them:
    
    
    define  
    do  
    for  
    foreach  
    while  
    repeat  
    until  
    if  
    then  
    else  
    elif  
    elsif  
    elseif  
    case  
    switch  
    
import java.io.*;
import java.util.*;

public class SolveE {

	public static void main(String[] args) throws IOException {
		new SolveE().solve();
	}
	void readA(int[][] a, int i) {
		a[i][0] = (Math.max(i, 0) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][1] = (Math.max(i, 1) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][2] = (Math.max(i, 2) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][3] = (Math.max(i, 3) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][4] = (Math.max(i, 4) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][5] = (Math.max(i, 5) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][6] = (Math.max(i, 6) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][7] = (Math.max(i, 7) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][8] = (Math.max(i, 8) <= n) ? in.nextInt() : Integer.MAX_VALUE;
		a[i][9] = (Math.max(i, 9) <= n) ? in.nextInt() : Integer.MAX_VALUE;
	}
	void fillF(int i, int[][] f, int[][] a) {
		f[i][0] = a[i][0];
		f[i][1] = a[i][1];
		f[i][2] = a[i][2];
		f[i][3] = a[i][3];
		f[i][4] = a[i][4];
		f[i][5] = a[i][5];
		f[i][6] = a[i][6];
		f[i][7] = a[i][7];
		f[i][8] = a[i][8];
		f[i][9] = a[i][9];
	}
	void calcF1(int[][] f, int i, int j, int k) {
		f[i][j] = Math.min(f[i][j], (k <= n) ? f[i][k] + f[k][j] : Integer.MAX_VALUE);
	}
	void calcF2(int[][] f, int i, int k) {
		int j = 0;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
		calcF1(f, i, j, k);
		j++;
	}
	void calcF3(int[][] f, int k) {
		int i = 0;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
		calcF2(f, i, k);
		i++;
	}
	Scanner in;
	int n;
	public void solve() throws IOException {
		in = new Scanner(System.in);
		
		n = in.nextInt() - 1;
		int[][] a = new int[10][10];

		int i = 0;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		readA(a, i);
		i++;
		
		int[][] f = new int[10][10];
		i = 0;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		fillF(i, f, a);
		i++;
		///
		
		int k = 0;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		calcF3(f, k);
		k++;
		
		
		
		////

		int ans = 0;
		i = 0;
		int j = 0;
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		// *
		j = 0;
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		// *
		ans = Math.max(ans, (i <= n && j <= n) ? f[i][j] : -1);
		j++;
		i++;
		// *
		System.out.print(ans);

	}

	public void run() {
		try {
			solve();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
}
