Cho \(G\) là một đồ thị có hướng không có chu trình, các đỉnh được đánh số từ 1 đến \(n\). Tại đỉnh thứ \(i\) có một số nguyên dương \(a_i\). Tha và Thu chơi một trò chơi như sau:

• Hai người chơi luân phiên nhau thực hiện lượt chơi, Tha đi trước
• Đến lượt mình, người chơi chọn một đỉnh \(i\) tùy ý, sau đó anh ta chia \(a_i\) cho một ước tùy ý (lớn hơn 1) của \(a_i\), sau đó với mỗi đỉnh \(j\) kề với \(i\) anh ta có thể tăng \(a_j\) lên một lượng là số nguyên không âm tùy ý (các đỉnh khác nhau có thể tăng một lượng khác nhau).
• Ai không thực hiện được lượt chơi hợp lệ nữa sẽ thua cuộc. Rõ ràng là trò chơi sẽ kết thúc sau hữu hạn bước, nên sẽ không có kết quả hòa.
  Biết rằng hai người chơi đều rất thông minh, hãy xác định ai là người chiến thắng

Input

Dòng đầu tiên chứa \(T\) là số lượng testcase, với mỗi testcase:

• Dòng đầu tiên chứa \(n\) \(m\): số đỉnh và số cung của đồ thị
• Dòng tiếp theo chứa \(a_1\) \(a_2\) \(\ldots\) \(a_n\)
• \(m\) dòng tiếp theo mỗi dòng chứa một cung: \(u\) \(v\)

Output

• Với mỗi testcase, ghi ra trên một dòng 1/0 tương ứng là Tha/Thu chiến thắng

Scoring

• Trong tất cả các test: Tổng \(n\) và tổng \(m\) trong \(T\) testcase đều không quá \(10^5\), \(1\leq a_i \leq 10^9\)
• Subtask \(1\) (\(10\%\) số điểm): \(m=0\) và \(a_i \leq 10^5\)
• Subtask \(2\) (\(20\%\) số điểm): \(m=0\)
• Subtask \(3\) (\(30\%\) số điểm): \(a_i \leq 10^5\)
• Subtask \(4\) (\(40\%\) số điểm): không ràng buộc gì thêm

Example

2 
3 0
2 8 9
9 11
2 3 4 5 6 7 8 9 1
1 2
2 3
3 4
4 5
5 6
1 3
3 6
1 7
7 8
8 9
9 3 

0
1