#13211Geonosis

After years of planning, the Galactic Empire has built the planetary fortress of Geonosis, a perfect prison for the leaders of the rebelion and a special place reserved for the evil Luke Skywalker. However, as it has been demonstrated with the failures of Death Star I and II, the fortress is not perfect and the evil Rebel Alliance plans to use a weakness detected in the communication towers surrounding Geonosis. To achieve their evil plans, the Rebel Alliance has stolen a map with the structure of the fortress. Geonosis has a communication complex formed by n towers. Each pair of the complex’s tower is connected by power lines that send messages at a w cost of energy. The rebels want to build the Rogue Two ship to destroy the fortress and rescue its prisoners. To achieve that, they have to destroy all the towers of the fortress. They have discovered that the power necessary to destroy a tower is equal to the sum of the minimum energy needed to send messages between each pair of the fortress towers, either directly or indirectly through other towers. In other words, if we define d(u, v) as the minimum energy to send a message from the tower u to the tower v, the power needed to destroy one tower will be: ∑ v,u,u̸ =v d(u, v) Note that once a tower is destroyed, it stops counting for this formula. On the other hand, the commander of the Rogue Two is very capricious so he wants to destroy the towers in a given order. Knowing the information of the communication towers in Geonosis and the order in which each tower will be destroyed, can you tell what is the power needed for the Rogue Two to complete it’s mission?

Input

The first line of the input contains an integer t, the number of test cases. Each test case begins with a line containing an integer n (1 ≤ n ≤ 500) the number of towers in the fortress. Next n lines contain n integers each, the j-th number in the i-th line wij (1 ≤ wij ≤ 104, wii = 0) represents the amount of energy that cost to send a message from tower i to tower j. Each test case ends with a line containing n distinct integers: x1, x2, . . . , xn (0 ≤ xi < n), the order in which the towers will be destroyed.

Output

For each test case print the amount of energy that Rogue Two will need to destroy the Geonosis fortress. Explanation: In the first test case, the energy needed to destroy the tower 0 is 89, to destroy the tower 1 is 7, to destroy the tower 2 is 0. So, the total energy needed by Rogue Two is 96.

3
3
0 35 58
12 0 5
1 2 0
0 1 2
3
0 9982 1413
8327 0 5612
3577 7893 0
1 0 2
4
0 50 10 30
4 0 23 58
2 1 0 5
67 24 25 0
0 3 1 2

96
41118
287