수위 아저씨의 고민

A 씨는 어느 회사 빌딩의 수위로 일한다. 매일 밤 12시가 되면 사무실에 켜져 있는 모든 등과 건물 옥상의 전광판을 끄고 퇴근한다.

이 빌딩은 구조가 독특하다. 각 층에는 같은 개수의 사무실이 일렬로 늘어서 있고, 건물 양쪽 끝에 엘리베이터가 하나씩 있다. 왼쪽 엘리베이터는 올라갈 때만, 오른쪽 엘리베이터는 내려갈 때만 탈 수 있다. 또한 옥상의 전광판을 끄기 전에는 왼쪽 엘리베이터만, 끈 뒤에는 오른쪽 엘리베이터만 이용할 수 있다.

따라서 이동은 다음 순서로 이루어진다. A 씨는 왼쪽 엘리베이터를 타고 1층에서 옥상까지 올라가며, 도중에 원하는 층에 내려 사무실 등을 끌 수 있다. 옥상에 도착하면 전광판을 끄는데, 이를 위해서는 옥상을 왼쪽 끝(왼쪽 엘리베이터)에서 오른쪽 끝(오른쪽 엘리베이터)까지 가로질러야 한다. 그런 다음 오른쪽 엘리베이터를 타고 다시 1층까지 내려오며, 도중에 원하는 층에 내려 남은 사무실 등을 끌 수 있다.

각 사무실의 등은 올라가며 왼쪽에서 접근해 끌 수도 있고, 내려오며 오른쪽에서 접근해 끌 수도 있다. 어느 층에 내려 등을 끄면 반드시 타고 온 엘리베이터로 돌아와야 다음 이동을 계속할 수 있다.

수위실에서 창문을 올려다보면 아직 켜져 있는 사무실을 모두 알 수 있으므로, A 씨는 소등을 시작하기 전에 이 정보로 경로를 계획한다. 켜져 있는 모든 사무실 등과 전광판을 끄기 위한 최소 이동 거리를 구하라.

거리는 다음과 같이 가정한다.

• 엘리베이터와 그 쪽 가장 바깥 사무실 사이의 거리는 $1$이다.
• 인접한 두 사무실 사이의 거리는 $1$이다.
• 엘리베이터로 한 층을 오르내리는 거리는 $1$이다.

입력은 표준입력으로 주어진다. 첫째 줄에 테스트케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트케이스는 다음과 같이 구성된다.

• 첫째 줄: 빌딩의 층수(옥상 제외) $F$ ($1 \le F \le 30$), 한 층의 사무실 수 $R$ ($1 \le R \le 30$), 등이 켜져 있는 사무실의 수 $N$ ($0 \le N \le F \times R$)이 공백으로 구분되어 주어진다.
• 다음 $N$개의 줄: 각 줄에 켜져 있는 사무실 하나의 위치가 층 번호 $a$ ($1 \le a \le F$)와 호수 $b$ ($1 \le b \le R$) 두 정수로 공백을 사이에 두고 주어진다. 호수는 왼쪽부터 차례로 $1, 2, \dots, R$이다.

같은 사무실(같은 층, 같은 호수)이 두 번 이상 주어지는 경우는 없다.

각 테스트케이스마다 모든 사무실 등과 전광판을 끄기 위한 최소 이동 거리를 한 줄에 하나씩 표준출력으로 출력한다.

전광판을 끄기 전에는 왼쪽 엘리베이터(올라가는 방향)만, 끈 뒤에는 오른쪽 엘리베이터(내려가는 방향)만 사용할 수 있다는 조건이 핵심이다. 이 조건 덕분에 켜져 있는 각 사무실을 올라가며 왼쪽에서 끌지, 내려오며 오른쪽에서 끌지를 층별로 독립적으로 결정할 수 있다.