你的一个发明家朋友最近建造了一艘宇宙飞船，并想用它来探索太空。在他的第一次航行中，他发现宇宙中充满了由某个外星种族创造的虫洞。这些虫洞不仅能让人旅行到极远的地方，而且还能将你送往很久以前的过去或遥远的未来。

在绘制了这些虫洞及其各自的端点后，你和你的朋友毅然决定登上他的宇宙飞船，前往你们想去的一个遥远地方。当然，你们希望尽可能早地到达目的地。问题是：最早的到达时间是多少？

输入格式

输入的第一行包含一个整数 $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$ ($-1\,000\,000 \le t, d \le 1\,000\,000$)，分别表示该虫洞的创建时间 $t$ 以及通过该虫洞旅行时的时间偏移 $d$。

所有坐标均为绝对值小于或等于 $10\,000$ 的整数，且任意两个点都不重合。

请注意，初始时间为零，且穿过虫洞是瞬间完成的。为了简化计算，两点之间的距离定义为它们的欧几里得距离（坐标差的平方和的平方根）向上取整到最接近的整数。你朋友的宇宙飞船以速度 1 行驶。

输出格式

对于每个测试用例，输出一行，包含一个整数：你到达目的地的最早时间。

样例

输入样例 1

2
0 0 0 100 0 0
2
1 1 0 1 2 0 -100 -2
0 1 0 100 1 0 -150 10
0 0 0 10 0 0
1
5 0 0 -5 0 0 0 0

输出样例 1

-89
10