Minimum Travel Distance

You are given several test cases. For each test case, you will receive the number of cities, an ordered list of cities to visit, and a distance matrix that gives the distance between every pair of cities. Your task is to compute the total travel distance when following the specified visiting order and then returning from the last city to the first city.

Formally, if the visiting order is \(p_1, p_2, \dots, p_n\) and the distance between city \(i\) and \(j\) is \(d_{ij}\), then the total travel distance \(D\) is given by:

$$D = \sum_{i=1}^{n-1} d_{p_i,p_{i+1}} + d_{p_n,p_1}$$

It is guaranteed that the distances are symmetric (i.e. the distance from \(i\) to \(j\) is the same as the distance from \(j\) to \(i\)).

inputFormat

The input is read from stdin and is structured as follows:

• The first line contains an integer \(T\) (the number of test cases).
• For each test case:
  • A line with an integer \(N\), representing the number of cities.
  • A line with \(N\) space-separated integers representing the visiting order (1-indexed).
  • Then \(N\) lines follow, each containing \(N\) space-separated integers. The \(j\)-th number in the \(i\)-th line is \(d_{ij}\), the distance from city \(i\) to city \(j\).

outputFormat

For each test case, output a single integer denoting the minimum travel distance on a separate line to stdout.## sample

1
3
1 2 3
0 10 15
10 0 20
15 20 0

45