Chuyển hàng

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 (hoặc của xe hai) khác nhau trong hai cách.

Input

Dữ liệu vào có cấu trúc:

• 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\)).

Ràng buộc:

• Có \(18\%\) số điểm tương ứng với \(N \le 500\); \(M \le 1\);

• Có \(16\%\) số điểm tương ứng với \(N \le 20\); \(M \le 40\);

• Có \(20\%\) số điểm tương ứng với \(\sum_{i=1}^{N} W_i \le 3 \times 10^3\);

• Có \(18\%\) số điểm tương ứng với \(\sum_{i=1}^{N} W_i \le 2 \times 10^5\);

• Có \(28\%\) số điểm còn lại không có ràng buộc gì thêm.

Output

In ra \(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

Input:

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

Output:

6
0

Note

Trường hợp 1: có \(6\) cách vận chuyển, tổng khối lượng của xe một lần lượt là \(3, 5, 7, 8, 10, 12\) (ví dụ xe một chở thùng \(1\) còn xe hai chở các thùng \(2, 3, 4, 5\)).

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