Firdaws 和 Fatinah 居住在一个拥有 $n$ 座城市的国家，城市编号从 $1$ 到 $n$。每座城市都有被绑架或抢劫的风险。

Firdaws 的家位于城市 $u$，Fatinah 的家位于城市 $v$。现在你需要找到从城市 $u$ 到城市 $v$ 的最短路径，且该路径不能经过任何风险值高于 $w$（由 Firdaws 给出的阈值）的城市。

输入格式

输入包含多个测试用例，第一行是一个正整数 $T$，表示测试用例的数量，最多为 $50$。

对于每个测试用例，第一行包含两个整数 $n$ ($1 \le n \le 200$)，表示城市数量；以及 $q$ ($1 \le q \le 2 \times 10^4$)，表示查询的数量。第二行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$，分别表示城市 $1$ 到 $n$ 的绑架或抢劫风险值。接下来的 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行的第 $j$ 个数 $d_{i,j}$ 表示城市 $i$ 到城市 $j$ 的距离。

接下来的 $q$ 行，每行给出一个独立的查询，包含三个整数 $u, v$ 和 $w$，含义如上所述。

保证 $1 \le r_i \le 10^5$，$1 \le d_{i,j} \le 10^5$ ($i \neq j$)，$d_{i,i} = 0$ 且 $d_{i,j} = d_{j,i}$。此外，每个查询满足 $1 \le u, v \le n$ 且 $1 \le w \le 10^5$。

输出格式

对于每个测试用例，首先输出一行 Case #x:，其中 $x$ 是从 $1$ 开始的测试用例编号。接下来的 $q$ 行，每行输出一个整数，表示对应查询的最短路径长度。

样例

输入 1

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

输出 1

Case #1:
0
1
3
0
1
2