Consider $4$ locations, numbered $0,1,2,$ and $3.$The following table shows the distances between the locations$\mathrm{.}012300562150132610132310$There exist $4!=24$ circuits that visit each location exactly once. However these circuits do notall have the same length. For example, the following two circuits differ in length:$10123$ and back to $0$ with length $5+1+1+2=9.2310$ and back to $2$ with length $1+3+5+6=15.$For this simple example, it is not hard to see that the shortest circuit length is $9.$ However, ifwe increase the number of locations, it gets harder to determine the length of the optimal circuit.The first line of the input of this problem contains a positive integer n which is the number oflocations. You may assume that n is at most $10.$ The next n lines contain the distance matrix.Because the distances are symmetric, only half the matrix is given. The output of the programmust be the length of the shortest circuit that visits all locations.