던전

용사가 함정으로 가득한 던전에 들어갔다. 던전은 $R$행 $C$열 격자이고, 각 칸은 좌표 $(r, c)$로 나타낸다. 여기서 $0 \le r < R$, $0 \le c < C$이다. 용사는 지금 $(0, 0)$에 있고 출구는 $(R-1, C-1)$에 있다.

1분마다 용사는 인접한 칸으로 움직일 수 있다. 두 칸이 변을 공유하면 인접하다. 제자리에 그대로 있어도 된다.

던전에는 함정이 $K$개 있다. 각 함정은 칸을 덮는 직사각형이고, 왼쪽 아래 칸 $(pr, pc)$와 오른쪽 위 칸 $(qr, qc)$로 주어진다. 이 함정은 $pr \le a \le qr$, $pc \le b \le qc$를 만족하는 모든 칸 $(a, b)$를 덮는다. 한 칸이 두 개 이상의 함정에 덮일 수도 있다.

함정이 덮은 칸에는 들어갈 수 없다. 게다가 함정도 움직인다. $i$번 함정의 속도는 $\langle dr_i, dc_i \rangle$이고 1분에 그만큼 이동한다. 어떤 함정의 왼쪽 아래가 $(pr, pc)$, 오른쪽 위가 $(qr, qc)$이면 1분 뒤 그 함정의 왼쪽 아래는 $(pr+dr_i, pc+dc_i)$, 오른쪽 위는 $(qr+dr_i, qc+dc_i)$가 된다. 단, 그 이동으로 함정의 일부라도 던전 밖으로 나가면 그 함정은 그 1분 동안 움직이지 않는다. 두 성분 중 한쪽만 적용하는 일은 없고 이동 전체가 취소된다. 이렇게 막힌 함정은 위치가 그대로이므로 그 뒤에도 계속 같은 자리에 머문다.

1분은 두 단계로 진행된다. 먼저 용사가 움직이고, 그다음 모든 함정이 움직인다. 용사가 함정 위에 있는지는 둘 다 움직인 뒤에 판정한다. 함정끼리 겹쳐도 이동은 멈추지 않는다. 시각 $0$에 $(0, 0)$을 덮는 함정은 없다.

용사가 함정에 한 번도 걸리지 않고 출구 칸에 도달하는 최소 시간을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 20$). 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

• 첫째 줄에 던전의 크기와 함정의 개수를 나타내는 세 정수 $R$, $C$, $K$가 주어진다 ($1 \le R, C \le 15$; $0 \le K \le 20$).
• 다음 $K$개 줄에 함정의 처음 위치와 속도가 주어진다. 각 줄에는 여섯 정수 $pr$, $pc$, $qr$, $qc$, $dr$, $dc$가 주어지고, 앞의 네 값은 함정의 왼쪽 아래와 오른쪽 위 좌표, 뒤의 두 값은 속도이다 ($0 \le pr < qr < R$; $0 \le pc < qc < C$; $-1 \le dr, dc \le 1$).

시각 $0$에 $(0, 0)$을 덮는 함정은 없음이 보장된다.

각 테스트 케이스마다 용사가 출구에 도달하는 최소 시간을 한 줄에 출력한다. 도달할 수 없으면 $-1$을 출력한다.

다음 그림은 $R = 5$, $C = 4$인 던전이다. 문자 A와 B는 함정이고 O는 용사이다. 그림은 $0$행이 맨 아래에 오도록 그렸다.

Fig (1)은 함정 A가 $(0, 2)$부터 $(1, 3)$까지, 함정 B가 $(2, 2)$부터 $(3, 3)$까지 덮고 두 함정 모두 정지한 경우다. Fig (2)와 Fig (3)은 함정 B의 속도가 $\langle 0, -1 \rangle$일 때 각각 1분 뒤와 2분 뒤의 모습이다. 2분 뒤부터는 함정 B가 더 왼쪽으로 갈 수 없어서 제자리에 머문다.