Mỗi ngày, công ty ABC cần vận chuyển N thùng hàng được đánh số từ 1 đến N.

Thùng hàng thứ i có khối lượng là W_i.

Hiện tại công ty chỉ có hai xe chở hàng. Toàn bộ N thùng hàng cần được chia cho hai xe để vận chuyển trong một lần.

Để đảm bảo quy tắc vận chuyển, công ty đưa ra M quy định. Quy định thứ j yêu cầu hai thùng hàng P_j và Q_j không được vận chuyển cùng một xe.

Hai cách vận chuyển được coi là khác nhau nếu tổng khối lượng hàng trên xe thứ nhất là khác nhau.

Yêu cầu

Hãy tính số giá trị tổng khối lượng khác nhau có thể xuất hiện trên xe thứ nhất khi chia các thùng hàng cho hai xe sao cho thỏa mãn tất cả các quy định.

Input

• Dữ liệu vào từ file TRANSPORT.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên T — số trường hợp cần tính
  \((1 \le T \le 10)\).

• Với mỗi trường hợp:

  • Dòng đầu tiên chứa hai số nguyên N, M
    \((2 \le N \le 5 \times 10^4,\ 0 \le M \le 10^5)\).

  • Dòng thứ hai chứa N số nguyên W_1, W_2, \dots, W_N
    \((W_i \ge 1,\ \sum W_i \le 10^6)\).

  • M dòng tiếp theo, mỗi dòng chứa hai số nguyên P_j, Q_j
    \((1 \le P_j, Q_j \le N,\ P_j \ne Q_j)\), biểu thị hai thùng hàng này không được xếp cùng một xe.

Output

• Gồm T dòng, dòng thứ i chứa một số nguyên là kết quả của trường hợp thứ i.

Example

2
5 2
3 2 3 2 5
1 2
1 3
3 3
5 7 8
1 3
2 3
1 2

6
0