Travelling Tom

Tom sells used popsicles from a stand, and business has been slow. He wants to fly around the world and sell his stock in other cities instead. He already has the list of cities he wants to visit and the price of every flight between them, so all that is left is working out what the trip costs.

Tom starts in the first city on the list and visits the cities in the listed order. After the last city he flies back to the city he started from. He may take extra flights through cities that are not next on the list, so a city on the list counts only when he reaches it in the correct relative order. For the list 1 0 2 the route 1 2 0 2 1 is valid, while 1 2 0 1 is not, because city 2 is never reached after city 0.

Compute the smallest total price of such a trip.

The first line contains the number of test cases $T$.

Each test case starts with a line containing the number of cities $N$. Cities are numbered from $0$ to $N-1$. The next line contains $N$ integers $a_1, a_2, \dots, a_N$, the order in which Tom visits the cities. The next $N$ lines contain $N$ integers each. The $j$-th integer on the $i$-th of those lines is $c_{ij}$, the price of the flight from city $i$ to city $j$. If no flight goes from city $i$ to city $j$, then $c_{ij}$ is $-1$.

• $0 < T \le 100$
• $0 < N \le 200$
• $0 \le a_i < N$, and the visiting order is always a permutation of $0$ to $N-1$
• $-1 \le c_{ij} \le 10000$
• $c_{ii} = 0$ for every city $i$

For each test case, print one line with the smallest total price of the trip. If Tom cannot complete the trip, print impossible instead.