很久很久以前，恶龙抓走了公主。为了拯救公主，勇者闯入了恶龙的巢穴。

恶龙的巢穴是一个长为 $n$、宽为 $m$ 的矩形区域。其左下角坐标为 $(0, 0)$，右上角坐标为 $(n, m)$。

勇者的位置是 $(x_s + 0.5, y_s + 0.5)$。 恶龙的位置是 $(x_t + 0.5, y_t + 0.5)$。

区域内有一些水平或垂直的墙壁。勇者可以在区域内向任意方向移动，但不能穿过墙壁，也不能穿过墙壁的端点。

勇者想要到达恶龙所在的位置，但可能会被墙壁阻挡。

幸运的是，勇者拥有特殊能力，每次使用特殊能力可以使一堵墙永久消失。

由于使用特殊能力需要消耗大量体力，勇者想知道，在能够到达恶龙位置的前提下，最少需要使用多少次特殊能力？

输入格式

第一行包含一个整数 $T(T \le 10)$，表示测试用例的数量。

每个测试用例的第一行包含 3 个整数 $n, m, K(1 \le n, m, K \le 15)$，分别表示矩形区域的长、宽以及墙壁的数量。

每个测试用例的第二行包含 4 个整数 $x_s, y_s, x_t, y_t(0 \le x_s, x_t < n, 0 \le y_s, y_t < m)$，表示勇者和恶龙的位置。

接下来的 $K$ 行，每行包含 4 个整数 $x_1, y_1, x_2, y_2(0 \le x_1, x_2 \le n, 0 \le y_1, y_2 \le m)$，表示墙壁的两个端点坐标，保证 $x_1 = x_2$ 或 $y_1 = y_2$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最少需要使用特殊能力的次数。

样例

输入 1

2
3 2 2
0 0 2 1
0 1 3 1
1 0 1 2
3 2 2
0 0 2 1
2 1 2 2
1 0 1 1

输出 1

2
0