Một bảng có ~n~ hàng đánh số từ ~0~ đến ~n-1~ và ~n~ cột đánh số từ ~0~ đến ~n-1~. Tọa độ của một ô thuộc hàng ~i~ và cột ~j~ là ~(i~, ~j)~. Mỗi ô nhận giá trị ~0~ hoặc ~1~. Trong bảng này, có ~m~ ô có giá trị ~0~. Các ô còn lại có giá trị ~1~. Hai người chơi một trò chơi bằng cách luân phiên thực hiện các bước đi. Người chơi thứ nhất thực hiện bước đi đầu tiên. Mỗi người chơi chỉ được thực hiện một bước đi mỗi lượt. Người chơi đến lượt mình mà không thể thực hiện bước đi nào nữa là người thua và người chơi còn lại là người chiến thắng. Một bước đi hợp lệ là một hành động đổi giá trị ~(0~ thành ~1~ hoặc ~1~ thành ~0)~ của bốn ô tại bốn góc của một hình chữ nhật nằm bên trong bảng thỏa mãn các điều kiện sau:

• hình chữ nhật phải có nhiều hơn ~1~ hàng và nhiều hơn ~1~ cột,
• ô với tọa độ hàng lớn nhất và tọa độ cột lớn nhất trong bốn ô phải có giá trị là ~0~.

Cho trước giá trị các ô trong một bảng, nhiệm vụ của bạn là viết một chương trình giúp người chơi thứ nhất xác định xem có tồn tại chiến thuật chơi để đảm bảo anh ta luôn thắng bất kể người chơi thứ hai chơi thế nào.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn ~20~ là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

• Với mỗi bộ dữ liệu, dòng đầu tiên chứa số nguyên ~n~ ~(0 < n < 1000)~ là kích thước của bảng.
• Dòng tiếp theo chứa số nguyên ~m~ ~(0 < m < 100)~.
• Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên ~x~, ~y~ ~(0 \leq x~, ~y < n)~ là tọa độ của một ô có giá trị ~0~.

Output

• Với mỗi bộ dữ liệu, ghi ra trên một dòng số ~1~ nếu tồn tại chiến thuật thắng cho người chơi thứ nhất, hoặc số ~0~ trong trường hợp ngược lại.

Sample Input

4
100
1
0 0
100
3
0 1
0 20
0 30
100
2
2 3
3 2
10
2
1 2
2 3

Sample Output

0
0
0
1