Một ngày nó admin page này bày tỏ sự bận bịu của mình với hiện nhân phương tây và nội dung cuộc hội thoại như sau:

tôi đi crawl đề đây 

crawl đề cũng mất time lắm á 

chọn contest => crawl => upload đề => submit thử từng câu => tạo contest 

đấy thấy bận bịu chưa

Vì thấy admin n giấu tên quá bận rộn nên hiền nhân phương tây đã cho anh một chuyến du lịch vào thế giới 2D để giải tỏa sau chuỗi ngày căng thẳng. Ở thế giới này có N cổng dịch chuyển có tọa độ là (x, y) biết rằng từ cổng này bạn có thể dịch chuyển đến một cổng bất kì. Vì còn quá trời dealine nên admin đang cố gắng đi ra khỏi thế giới này càng sớm càng tốt nhưng do code quá nhiều nên anh ấy không còn đi như người bth mà chỉ có thể đi theo hướng (x+d, y) (d≥1).

Nhằm giúp admin n giấu tên ở lại thế giới lâu hơn nên ngài quyết định kết nối các cặp cổng dịch chuyển sao cho tạo thành một chuỗi lặp vô tận.

VD: ta có 2 cổng A(1,1) B(3,1) kết nối với nhau và admin xuất phát ở tọa độ (2,1). Admin di chuyển theo hướng (x+d, y) (d≥1) nên bước tiếp theo anh ta sẽ đến B(3,1). cổng B kết nối với cổng A nên sẽ dịch chuyển đến A(1,1) và sau đó admin bận bịu lại đi tiếp thế là anh ta bị mắc vào một vòng lặp vô tận.

*Chú ý: 2 cổng A và B kết nối thì ta có thể đi từ A đến B và ngược lại từ B đến A Nhằm tạo một thế giới đẹp nhất có thể hiền nhân hỏi bạn có bao nhiêu cách ghép các cặp cổng để admin vĩnh viễn ở lại

2≤N ≤12

0≤x, y≤1e9

Sample Input 1

4
0 0
1 0
1 1
0 1

Sample Output 1

2

Ta đánh số các đỉnh lần lượt từ 1..4 Từ đó ta có các cách ghép như sau để admin bận bịu mãi mãi bận bịu

.1→3 và 2→4

.1→2và 3->4