Acesrc 和他的女朋友是南京大学著名的甜食爱好者。他们经常在南京新街口附近的街道上漫步，品尝章鱼烧。

新街口是南京的中心商业区，由 $n$ 个十字路口和连接其中一些路口的 $m$ 条街道组成。每条街道旁都有一家章鱼烧店，Acesrc 对每家店都有一个偏好值。这些街道是双向的。

Acesrc 和他的女朋友选择一对十字路口作为起点和终点；此外，他们会选择这两点之间的一条路径，并沿着路径行走。路径中每个十字路口最多出现一次。每当他们遇到一家章鱼烧店，就会从该店购买一份章鱼烧。然而，他们最多只能保留两份章鱼烧。如果购买一份章鱼烧后他们持有的章鱼烧超过两份，他们会丢弃其中偏好值最小的一份。

到达终点后，他们开始享用章鱼烧。Acesrc 总是吃掉偏好值较低的那一份；然而，如果他们只买到了一份章鱼烧，可怜的 Acesrc 将无物可吃。聪明的 Acesrc 想知道，给定起点和终点，他所吃到的章鱼烧的偏好值最小可能是多少。你能告诉他这个值吗？

输入格式

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

对于每个测试用例，第一行包含三个整数 $n, m, q$ ($1 \le n, q \le 10^5, 1 \le m \le 2 \times 10^5$)，分别表示十字路口的数量、街道的数量以及查询的数量。接下来的 $m$ 行，每行包含三个整数 $x, y, w$ ($1 \le x, y \le n, x \neq y, 1 \le w \le 10^9$)，表示连接第 $x$ 个和第 $y$ 个十字路口的街道，且该街道旁的章鱼烧店偏好值为 $w$。可能存在多条街道连接同一对十字路口。最后 $q$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示一个查询，起点为第 $u$ 个十字路口，终点为第 $v$ 个十字路口。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和不超过 $2.5 \times 10^5$，且 $m$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每个查询，在一行中输出答案。如果 Acesrc 可能无物可吃，输出 0；如果给定起点和终点之间没有路径，输出 -1。

样例

样例输入 1

1
4 2 3
1 2 2
2 3 3
1 2
1 3
1 4

样例输出 1

0
2
-1