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~. Được biết, thùng hàng ~i~ nặng ~W_i~ ki-lô-gam, và ~\sum_{i=1}^{N} W_i~ không vượt quá ~10^6~ ki-lô-gam. Hiện tại, ở công ty chỉ có hai chiếc xe chở hàng, vì tính chất của công việc, toàn bộ ~N~ thùng này cần được vận chuyển trong một lần. Cả hai xe đều đảm bảo tải trọng để chở ~N~ thùng hàng.

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

Yêu cầu: Hãy tính số cách khác nhau để chia các thùng hàng ra cho hai xe mà vẫn tuân thủ các quy định. Hai cách vận chuyển được gọi là khác nhau nếu tổng khối lượng vận chuyển của xe một và tổng khối lượng vận chuyển của xe hai khác nhau trong hai cách.

Input

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

• ~T~ nhóm dòng tiếp theo, mỗi nhóm dòng tương ứng một trường hợp có cấu trúc như sau:

  • Dòng đầu 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, số thứ ~i~ là giá trị của ~W_i~ ~(W_i \ge 1; \sum_{i=1}^{N} W_i \le 10^6)~.

  • ~M~ dòng tiếp theo, dòng thứ ~j~ gồm hai số nguyên ~P_j, Q_j~ ~(1 \le P_j, Q_j \le N; P_j \ne Q_j)~.

Output

~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~.

Scoring

Sample Input 1

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

Sample Output 1

6
0

Notes

• Trường hợp 1: Có ~6~ cách vận chuyển như sau:

  Xe 1	Xe 2
  ~3~	~2, 3, 2, 5~
  ~3, 2~	~2, 3, 5~
  ~3, 2, 5~	~2, 3~
  ~2, 3, 2~	~3, 5~
  ~2, 3, 2, 5~	~3~
  ~3, 5~	~2, 3, 2~

• Trường hợp 2: Không có cách vận chuyển phù hợp.