시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

루니와 치차리토는 군사 전략 게임을 하고 있다. 이 게임은 평평한 세계 지도를 지도로 사용한다. 게임을 시작하면서 치차리토는 자신의 군대를 배치한다. 

그 다음 루니는 다음과 같은 규칙을 따르면서 전략점을 정한다.

1. 모든 전략점은 |x| + |y| < N을 만족하는 (x, y)위에 있다. (x와 y는 정수)

2. 루니는 전략점을 양수 개수 만큼 고를 수 있다.

3. 모든 전략점 서로 달라야 한다.

4. 각 전략점은 치차리토의 군대가 있는 곳과 겹치면 안된다.

5. 전략점은 모두 서로 연결되어 있어야 한다. (다른 전략점을 통해서 연결되어 있을 수도 있다)

(x1, y1)와 (x2, y2)가 |x1-x2| + |y1-y2| = 1을 만족한다면, 두 점은 연결되어 있는 것이다.

만약, A, B, C가 전략점이고, A와 B가 연결되어 있고, B와 C가 연결되어 있다면, A와 C도 연결되어 있는 것이다.

루니가 전략점을 고를 수 있는 방법의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 M이 공백으로 구분되어져서 주어진다. N은 첫번째 규칙에 나와있는 N이고, M은 치차리토가 배치한 군대의 수이다.

둘째 줄부터 M개의 줄에는 치차리토가 배치한 군대의 좌표 (Xk, Yk)가 주어진다. 이 두 수는 공백으로 구분되어져 있다.

  • 1 ≤ T ≤ 74,
  • 1 ≤ N ≤ 7,
  • 1 ≤ M ≤ 225,
  • -7 ≤ Xk, Yk ≤ 7,
  • 모든 (Xk, Yk) 서로 다르다.

출력

각 테스트 케이스에 대해서 루니가 전략점을 고를 수 있는 방법을 출력한다.

예제 입력 1

2
2 1
7 7
2 3
0 0
4 -7
7 -4

예제 출력 1

20
4
W3sicHJvYmxlbV9pZCI6IjM3NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWI3YjUgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI4ZThcdWIyYzhcdWM2NDAgXHVjZTU4XHVjYzI4XHViOWFjXHVkMWEwXHViMjk0IFx1YWQ3MFx1YzBhYyBcdWM4MDRcdWI3YjUgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHVkM2M5XHVkM2M5XHVkNTVjIFx1YzEzOFx1YWNjNCBcdWM5YzBcdWIzYzRcdWI5N2MgXHVjOWMwXHViM2M0XHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3NFx1YzExYyBcdWNlNThcdWNjMjhcdWI5YWNcdWQxYTBcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YWQ3MFx1YjMwMFx1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgXHViOGU4XHViMmM4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YmE3NFx1YzExYyBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDQgXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPjEuIFx1YmFhOFx1YjRlMCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDAgfHh8ICsgfHl8ICZsdDsgTlx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgKHgsIHkpXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC4gKHhcdWM2NDAgeVx1YjI5NCBcdWM4MTVcdWMyMTgpPFwvcD5cclxuXHJcbjxwPjIuIFx1YjhlOFx1YjJjOFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDQgXHVjNTkxXHVjMjE4IFx1YWMxY1x1YzIxOCBcdWI5Y2NcdWQwN2MgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjMuIFx1YmFhOFx1YjRlMCBcdWM4MDRcdWI3YjVcdWM4MTAgXHVjMTFjXHViODVjIFx1YjJlY1x1Yjc3Y1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjQuIFx1YWMwMSBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDAgXHVjZTU4XHVjYzI4XHViOWFjXHVkMWEwXHVjNzU4IFx1YWQ3MFx1YjMwMFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVhY2ZjIFx1YWNiOVx1Y2U1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjUuIFx1YzgwNFx1YjdiNVx1YzgxMFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHViMmU0XHViOTc4IFx1YzgwNFx1YjdiNVx1YzgxMFx1Yzc0NCBcdWQxYjVcdWQ1NzRcdWMxMWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0KTxcL3A+XHJcblxyXG5cclxuXHJcbjxwPih4MSwgeTEpXHVjNjQwICh4MiwgeTIpXHVhYzAwIHx4MS14MnwgKyB8eTEteTJ8ID0gMVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YjQ1MCBcdWM4MTBcdWM3NDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBBLCBCLCBDXHVhYzAwIFx1YzgwNFx1YjdiNVx1YzgxMFx1Yzc3NFx1YWNlMCwgQVx1YzY0MCBCXHVhYzAwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIEJcdWM2NDAgQ1x1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHViYTc0LCBBXHVjNjQwIENcdWIzYzQgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViOGU4XHViMmM4XHVhYzAwIFx1YzgwNFx1YjdiNVx1YzgxMFx1Yzc0NCBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIE1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjY2FiXHViYzg4XHVjOWY4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgTlx1Yzc3NFx1YWNlMCwgTVx1Yzc0MCBcdWNlNThcdWNjMjhcdWI5YWNcdWQxYTBcdWFjMDAgXHViYzMwXHVjZTU4XHVkNTVjIFx1YWQ3MFx1YjMwMFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNThcdWNjMjhcdWI5YWNcdWQxYTBcdWFjMDAgXHViYzMwXHVjZTU4XHVkNTVjIFx1YWQ3MFx1YjMwMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgKFhrLCBZaylcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNDUwIFx1YzIxOFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBUICZsZTsgNzQsPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgNyw8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyAyMjUsPFwvbGk+XHJcblx0PGxpPi03ICZsZTsgWGssIFlrICZsZTsgNyw8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIChYaywgWWspIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViOGU4XHViMmM4XHVhYzAwIFx1YzgwNFx1YjdiNVx1YzgxMFx1Yzc0NCBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3NDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgQ29tcHV0ZXIgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+Sm9obiBhbmQgQnJ1cyBhcmUgcGxheWluZyBhIG1pbGl0YXJ5IHN0cmF0ZWdpYyBnYW1lIG9uIGEgUEMuIFRoZSBnYW1lIGlzIHBsYXllZCBvbiB0aGUgZmxhdCB3b3JsZCBtYXAuIEF0IHRoZSBiZWdpbm5pbmcgb2YgdGhlIGdhbWUgQnJ1cyBwbGFjZXMgaGlzIGFybXkuIFRoZW4gSm9obiBoYXMgdG8gY2hvb3NlIHN0cmF0ZWdpYyBwb2ludHMgZm9yIGhpcyBhcm15IGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmVhY2ggc3RyYXRlZ2ljIHBvaW50IG11c3QgYmUgYSBsYXR0aWNlIHBvaW50ICh4LCB5KSAoYSBsYXR0aWNlIHBvaW50IGlzIGEgcG9pbnQgd2l0aCBpbnRlZ2VyIGNvb3JkaW5hdGVzKSBzdWNoIHRoYXQgfHh8ICsgfHl8ICZsdDsgTjs8XC9saT5cclxuXHQ8bGk+Sm9obiBjYW4gY2hvb3NlIGFueSBwb3NpdGl2ZSBudW1iZXIgb2Ygc3RyYXRlZ2ljIHBvaW50czs8XC9saT5cclxuXHQ8bGk+YWxsIHRoZSBzdHJhdGVnaWMgcG9pbnRzIG11c3QgYmUgZGlzdGluY3Q7PFwvbGk+XHJcblx0PGxpPmVhY2ggb2YgdGhlIHN0cmF0ZWdpYyBwb2ludHMgbXVzdCBiZSBmcmVlIChpLmUuIG5vdCBvY2N1cGllZCBieSBCcnVzJnJzcXVvO3MgYXJteSk7PFwvbGk+XHJcblx0PGxpPmVhY2ggcGFpciBvZiBkaWZmZXJlbnQgc3RyYXRlZ2ljIHBvaW50cyBtdXN0IGJlIGNvbm5lY3RlZCAocG9zc2libHkgdmlhIHNvbWUgb3RoZXIgc3RyYXRlZ2ljIHBvaW50cykuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SGVyZSB0d28gZGlmZmVyZW50IGxhdHRpY2UgcG9pbnRzICh4MSwgeTEpIGFuZCAoeDIsIHkyKSBhcmUgY29ubmVjdGVkIGlmIHx4MSAmbmRhc2g7IHgyfCArIHx5MSAmbmRhc2g7IHkyfCA9IDEuIElmIEEsIEIgYW5kIEMgYXJlIHN0cmF0ZWdpYyBwb2ludHMsIEEgYW5kIEIgYXJlIGNvbm5lY3RlZCwgQiBhbmQgQyBhcmUgY29ubmVjdGVkLCB0aGVuIEEgYW5kIEMgYXJlIGFsc28gY29ubmVjdGVkLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gZmluZCB0aGUgbnVtYmVyIG9mIHdheXMgZm9yIEpvaG4gdG8gY2hvb3NlIHN0cmF0ZWdpYyBwb2ludHMgZm9yIGhpcyBhcm15LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgc2luZ2xlIGludGVnZXIgVCAmbmRhc2g7IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIE4gYW5kIE0gc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBOIGlzIHRoZSBudW1iZXIgbWVudGlvbmVkIGluIHRoZSBmaXJzdCBydWxlLiBNIGlzIHRoZSBudW1iZXIgb2YgbGF0dGljZSBwb2ludHMgb24gdGhlIHdvcmxkIG1hcCBhbHJlYWR5IG9jY3VwaWVkIGJ5IEJydXMmcnNxdW87cyBhcm15LiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgWDxzdWI+azxcL3N1Yj4gYW5kIFk8c3ViPms8XC9zdWI+IHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gRWFjaCBsYXR0aWNlIHBvaW50IChYPHN1Yj5rPFwvc3ViPiwgWTxzdWI+azxcL3N1Yj4pIGlzIG9jY3VwaWVkIGJ5IEJydXMmcnNxdW87cyBhcm15LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBUICZsZTsgNzQsPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgNyw8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyAyMjUsPFwvbGk+XHJcblx0PGxpPi03ICZsZTsgWGssIFlrICZsZTsgNyw8XC9saT5cclxuXHQ8bGk+YWxsIChYaywgWWspIHdpbGwgYmUgZGlzdGluY3QuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2Ygd2F5cyBmb3IgSm9obiB0byBjaG9vc2Ugc3RyYXRlZ2ljIHBvaW50cyBmb3IgaGlzIGFybXkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d