웜홀

당신의 친구가 우주선을 만들어 우주를 탐험하려고 합니다. 첫 항해에서 그는 우주가 웜홀로 가득 차 있다는 것을 발견했습니다. 웜홀은 입구에서 출구로 즉시 이동시켜 줄 뿐만 아니라, 과거나 미래의 어떤 시점으로 데려다주기도 합니다.

모든 웜홀의 입구와 출구를 지도로 정리한 뒤, 당신과 친구는 먼 목적지로 날아가기로 하고 가능한 한 빨리 도착하고자 합니다. 출발 지점, 목적지, 그리고 모든 웜홀이 주어질 때, 목적지에 도착할 수 있는 가장 빠른 시각을 구하세요.

첫 번째 줄에는 테스트 케이스의 수 $c$ ($1 \le c \le 200$)가 주어집니다. 각 테스트 케이스는 다음과 같이 주어집니다.

• 첫 번째 줄에는 두 좌표 $x_0\ y_0\ z_0$와 $x_1\ y_1\ z_1$이 주어지며, 각각 출발 지점과 목적지의 좌표입니다.
• 다음 줄에는 웜홀의 수 $n$ ($0 \le n \le 50$)이 주어집니다.
• 이어지는 $n$개의 줄에는 각 웜홀이 두 좌표 $x_s\ y_s\ z_s$(입구)와 $x_e\ y_e\ z_e$(출구), 그리고 두 정수 $t$와 $d$ ($-1000000 \le t, d \le 1000000$)로 주어집니다. $t$는 웜홀이 생성되는 시각, $d$는 웜홀을 통과할 때 적용되는 시간 이동량입니다.

모든 좌표는 절댓값이 $10000$ 이하인 정수이며, 주어진 점들 중 같은 점은 없습니다.

시각은 $0$에서 시작합니다. 우주선은 속도 $1$로 이동하며, 두 점 사이의 거리는 유클리드 거리를 올림한 값, 즉 $\lceil \sqrt{(\Delta x)^2 + (\Delta y)^2 + (\Delta z)^2} \rceil$입니다. 웜홀 통과는 순간적으로 일어납니다. 웜홀 $i$는 시각 $T \ge t_i$일 때에만 진입할 수 있으며(진입 전에 기다릴 수 있습니다), 진입하면 시각 $T + d_i$에 그 출구 지점에 있게 됩니다.

각 테스트 케이스마다 목적지에 도착할 수 있는 가장 빠른 시각을 정수 하나로 한 줄에 출력하세요. 이 값은 음수일 수 있습니다.