Parking Building

Time limit1sMemory limit128 MB

Summary

Simulate an elevator and rotating conveyor belts to compute total retrieval time for cars fetched in customer order.

Level: Medium4 of 10
Topics: Simulation, Implementation, Math
Solved: No attempts yet

Problem

The parking building works on a simple principle. A driver parks the car in the elevator at the entrance of the parking tower and steps out. The elevator and the conveyor belt then find an empty parking space and move the car there. The car stays there until the driver returns. When the driver comes back, the elevator and the conveyor belt locate that car and bring it back to the entrance.

The layout is also simple. A single elevator sits at the center of the building, and cars move between floors using this elevator. Each floor has one large circular conveyor belt, and the cars rest on this belt. The belt can turn clockwise or counterclockwise. When the elevator reaches a floor, it becomes one slot of that floor's belt, so a car can move past the slot where the elevator is.

Toward the end of the day, many people come to retrieve their cars. Customers pick up their cars in the order they arrive. The elevator goes up to the floor holding the car, the belt carries that car into the elevator's slot, and then the elevator descends to floor 1 to hand the car to the customer. Write a program that computes the total time for all customers to retrieve their cars. Moving the elevator by one floor takes 10 seconds, and turning the belt by one slot clockwise or counterclockwise takes 5 seconds.

Input

The first line contains the number of test cases, at most 100. The first line of each test case contains the height $h$ of the parking building and the length $l$ of the conveyor belt ( $1 \le h \le 50$ , $2 \le l \le 50$ ). Each of the next $h$ lines contains $l$ integers describing the cars in the building. The $j$ -th number on the $i$ -th line denotes the car at position $j$ on floor $i$ . A value of $-1$ means that slot is empty, while any other value $r$ means the car belonging to the $r$ -th customer. Customers receive their cars on floor 1, and the elevator starts empty at the first position on floor 1. Every input is guaranteed to describe a valid building in which all referenced cars are present.

Output

For each test case, print on its own line the total time for all customers to retrieve their cars.

Examples7

Example 1

Input

2
1 5
-1 2 1 -1 3
3 6
-1 5 6 -1 -1 3
-1 -1 7 -1 2 9
-1 10 4 1 8 -1

Expected output

25
320

Example 2
Input
```
1
1 2
-1 1
```
Expected output
```
5
```
Example 3
Input
```
1
1 2
1 -1
```
Expected output
```
0
```
Example 4
Input
```
1
3 3
-1 -1 3
-1 2 -1
1 -1 -1
```
Expected output
```
70
```
Example 5
Input
```
1
1 4
-1 -1 1 -1
```
Expected output
```
10
```
Example 6
Input
```
2
1 2
-1 1
1 2
1 -1
```
Expected output
```
5
0
```
Example 7
Input
```
1
1 6
3 1 2 -1 -1 -1
```
Expected output
```
20
```