Cho một đồ thị vô hướng có trọng số, với trọng số cạnh thể hiện khả năng thông qua của cạnh đó.

Bây giờ cho một số ~x~, hãy tính xem có bao nhiêu cặp ~\left(s, t\right)~ không tính thứ tự trong đồ thị thỏa mãn ~minCut\left(s,t\right) \leq x~.

Một nhát cắt là một cách chia các đỉnh của đồ thị thành ~2~ tập hợp sao cho ~s~ và ~t~ thuộc ~2~ tập khác nhau sau khi chia.

Trong đồ thị có trọng số, độ lớn của một nhát cắt được định nghĩa là tổng trọng số của các cạnh bị nhát cắt cắt qua. ~minCut~ là một nhát cắt có độ lớn nhỏ nhất có thể.

Input

• Dòng đầu chứa ~T~, số lượng test.
• Với mỗi test, dòng đầu chứa ~2~ số nguyên ~n~ và ~m~, thể hiện số lượng đỉnh và số lượng cạnh của đồ thị.
• ~m~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~u,v,c~ thể hiện một cạnh vô hướng với khả năng thông qua ~c~ giữa đỉnh ~u~ và ~v~ ~\left(1 \leq u,v \leq n\right)~.
• Dòng tiếp theo chứa ~q~, số lượng câu hỏi. ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~.
• Lưu ý: có thể có nhiều cạnh giữa một cặp đỉnh.

Output

• Chứa ~q~ dòng, mỗi dòng chứa ~1~ số nguyên thể hiện số lượng cặp không thứ tự ~\left(s, t\right)~ tương ứng cho câu hỏi đó. In ra một dòng trống giữa các test.

Giới hạn

• Input Set ~1~: ~T \leq 15,\text{ } n \leq 40,\text{ } m \leq 400,\text{ } q \leq 10~.
• Input Set ~2~: ~T \leq 20,\text{ } n \leq 150,\text{ } m \leq 3000,\text{ } q \leq 30~.
• Trọng số các cạnh không quá ~10^6~.

Sample Input

1
5 0
1
0

Sample Output

10