小 A 有一张 $n$ 个点 $m$ 条边的有向图，每条边形如 $u_i, v_i, w_i, d_i$，其中 $u_i, v_i$ 分别表示边的起点与终点，$w_i$ 是边的权值，而 $d_i$ 是边的长度。并不保证所有边的权值两两不同。
小 A 想在图中找到一条路径，可以经过重复的点，使得路径上每条边的权值均在 $[l, r]$ 中，且边权严格递增。他还希望路径上所有边的长度总和尽可能地大。
现在有 $q$ 组询问，每次给出 $[l, r]$，请帮小 A 求出符合条件的路径长度最大是多少。
本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。
对于每组测试数据，
第一行三个正整数 $n, m, q$，分别表示顶点个数、边数与询问个数。
接下来 $m$ 行，每行四个正整数 $u_i, v_i, w_i, d_i$（保证 $u_i \neq v_i$），描述一条边。
接下来 $q$ 行，每行两个正整数 $l, r$（保证 $l \leq r$），表示一次询问。
对于每次询问输出一行一个整数，表示对应询问的答案。
2 5 5 5 1 3 4 4 5 2 3 3 2 3 2 1 3 4 1 2 2 4 5 3 1 5 3 5 4 4 2 4 1 3 3 10 5 2 3 11 13 2 3 7 8 1 3 13 19 2 3 16 18 3 2 20 19 3 2 5 6 2 1 10 11 3 1 18 14 3 1 6 1 3 2 1 17 3 20 5 7 6 19 15 20 1 9\n · · \n · · · \n · · · \n · · · \n · · · \n · · · \n · \n · \n · \n · \n · \n · · \n · · · \n · · · \n · · · \n · · · \n · · · \n · · · \n · · · \n · · · \n · · · \n · · · \n · \n · \n · \n · \n · \n
6 6 4 4 3 55 14 44 37 25\n \n \n \n \n \n \n \n \n \n
对于所有数据，$1 \leq T \leq 5$，$2 \leq n \leq 50$，$1 \leq m \leq 5 \times 10 ^ 4$，$1 \leq q \leq 5 \times 10 ^ 5$，$1 \leq u_i, \ v_i \leq n$，$1 \leq l, \ r, \ w_i, \ d_i \leq 10 ^ 9$。