Xiaobai learned a new concept in his graph theory class: the minimum cut. After class, he wrote the following in his notebook:

"For a graph, a partition of the nodes in the graph divides all nodes into two parts. If nodes $s$ and $t$ are not in the same part, this partition is called an $s,t$-cut. For a weighted graph, the capacity of this cut is defined as the sum of the weights of all edges that have their endpoints in different parts. The minimum $s,t$-cut refers to the cut with the minimum capacity among all $s,t$-cuts."

Given an undirected graph, Xiaobai has several questions of the form: "How many pairs of points in the graph have a minimum cut capacity not exceeding $x$?" Although Xiaolan would like to answer these questions, he has been busy digging wood blocks lately. As Xiaolan's friend, you have been given this task.

Input

The first line of the input file contains a single positive integer $T$, representing the number of test cases.

For each test case: The first line contains two integers $n$ and $m$, representing the number of vertices and edges in the graph. The next $m$ lines each contain three positive integers $u, v, c$ ($1 \le u, v \le n, 0 \le c \le 10^6$), representing an undirected edge $(u, v)$ with weight $c$. The next line contains an integer $q$, representing the number of queries. The next $q$ lines each contain an integer $x$, with the same meaning as described in the problem statement.

Output

For each test case, output $q$ lines, where the $i$-th line represents the answer to the $i$-th query. For pairs $(p, q)$ and $(q, p)$, count them only once (see the example).

Constraints

For 30% of the data: $n \le 40, m \le 400, q \le 10$. For 100% of the data: $T \le 10, n \le 150, m \le 3000, q \le 30$, and $x$ is within the range of a 32-bit signed integer. There may be multiple edges between two points in the graph.

Examples

Input 1

1
5 0
1
0

Output 1

10