시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG5cclxuXHJcbjxwPjEuIFx1YmFhOFx1YjRlMCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDAgfHh8ICsgfHl8ICZsdDsgTlx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgKHgsIHkpXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC4gKHhcdWM2NDAgeVx1YjI5NCBcdWM4MTVcdWMyMTgpPFwvcD5cclxuXHJcbjxwPjIuIFx1YjhlOFx1YjJjOFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDQgXHVjNTkxXHVjMjE4IFx1YWMxY1x1YzIxOCBcdWI5Y2NcdWQwN2MgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjMuIFx1YmFhOFx1YjRlMCBcdWM4MDRcdWI3YjVcdWM4MTAgXHVjMTFjXHViODVjIFx1YjJlY1x1Yjc3Y1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjQuIFx1YWMwMSBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDAgXHVjZTU4XHVjYzI4XHViOWFjXHVkMWEwXHVjNzU4IFx1YWQ3MFx1YjMwMFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVhY2ZjIFx1YWNiOVx1Y2U1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD41LiBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDAgXHViYWE4XHViNDUwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gKFx1YjJlNFx1Yjk3OCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDQgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNCk8XC9wPlxyXG5cclxuXHJcblxyXG48cD4oeDEsIHkxKVx1YzY0MCAoeDIsIHkyKVx1YWMwMCB8eDEteDJ8ICsgfHkxLXkyfCA9IDFcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0XHViYTc0LCBcdWI0NTAgXHVjODEwXHVjNzQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgQSwgQiwgQ1x1YWMwMCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NzRcdWFjZTAsIEFcdWM2NDAgQlx1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBCXHVjNjQwIENcdWFjMDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNFx1YmE3NCwgQVx1YzY0MCBDXHViM2M0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjhlOFx1YjJjOFx1YWMwMCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDQgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzhcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjA5OFx1YzY0MFx1Yzc4OFx1YjI5NCBOXHVjNzc0XHVhY2UwLCBNXHVjNzQwIFx1Y2U1OFx1Y2MyOFx1YjlhY1x1ZDFhMFx1YWMwMCBcdWJjMzBcdWNlNThcdWQ1NWMgXHVhZDcwXHViMzAwXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U1OFx1Y2MyOFx1YjlhY1x1ZDFhMFx1YWMwMCBcdWJjMzBcdWNlNThcdWQ1NWMgXHVhZDcwXHViMzAwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyAoWGssIFlrKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI0NTAgXHVjMjE4XHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyA3NCw8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyA3LDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTSAmbGU7IDIyNSw8XC9saT5cclxuXHQ8bGk+LTcgJmxlOyBYaywgWWsgJmxlOyA3LDxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgKFhrLCBZaykgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWI4ZThcdWIyYzhcdWFjMDAgXHVjODA0XHViN2I1XHVjODEwXHVjNzQ0IFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzQzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIENvbXB1dGVyIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkpvaG4gYW5kIEJydXMgYXJlIHBsYXlpbmcgYSBtaWxpdGFyeSBzdHJhdGVnaWMgZ2FtZSBvbiBhIFBDLiBUaGUgZ2FtZSBpcyBwbGF5ZWQgb24gdGhlIGZsYXQgd29ybGQgbWFwLiBBdCB0aGUgYmVnaW5uaW5nIG9mIHRoZSBnYW1lIEJydXMgcGxhY2VzIGhpcyBhcm15LiBUaGVuIEpvaG4gaGFzIHRvIGNob29zZSBzdHJhdGVnaWMgcG9pbnRzIGZvciBoaXMgYXJteSBhY2NvcmRpbmcgdG8gdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5lYWNoIHN0cmF0ZWdpYyBwb2ludCBtdXN0IGJlIGEgbGF0dGljZSBwb2ludCAoeCwgeSkgKGEgbGF0dGljZSBwb2ludCBpcyBhIHBvaW50IHdpdGggaW50ZWdlciBjb29yZGluYXRlcykgc3VjaCB0aGF0IHx4fCArIHx5fCAmbHQ7IE47PFwvbGk+XHJcblx0PGxpPkpvaG4gY2FuIGNob29zZSBhbnkgcG9zaXRpdmUgbnVtYmVyIG9mIHN0cmF0ZWdpYyBwb2ludHM7PFwvbGk+XHJcblx0PGxpPmFsbCB0aGUgc3RyYXRlZ2ljIHBvaW50cyBtdXN0IGJlIGRpc3RpbmN0OzxcL2xpPlxyXG5cdDxsaT5lYWNoIG9mIHRoZSBzdHJhdGVnaWMgcG9pbnRzIG11c3QgYmUgZnJlZSAoaS5lLiBub3Qgb2NjdXBpZWQgYnkgQnJ1cyZyc3F1bztzIGFybXkpOzxcL2xpPlxyXG5cdDxsaT5lYWNoIHBhaXIgb2YgZGlmZmVyZW50IHN0cmF0ZWdpYyBwb2ludHMgbXVzdCBiZSBjb25uZWN0ZWQgKHBvc3NpYmx5IHZpYSBzb21lIG90aGVyIHN0cmF0ZWdpYyBwb2ludHMpLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkhlcmUgdHdvIGRpZmZlcmVudCBsYXR0aWNlIHBvaW50cyAoeDEsIHkxKSBhbmQgKHgyLCB5MikgYXJlIGNvbm5lY3RlZCBpZiB8eDEgJm5kYXNoOyB4MnwgKyB8eTEgJm5kYXNoOyB5MnwgPSAxLiBJZiBBLCBCIGFuZCBDIGFyZSBzdHJhdGVnaWMgcG9pbnRzLCBBIGFuZCBCIGFyZSBjb25uZWN0ZWQsIEIgYW5kIEMgYXJlIGNvbm5lY3RlZCwgdGhlbiBBIGFuZCBDIGFyZSBhbHNvIGNvbm5lY3RlZC48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIG51bWJlciBvZiB3YXlzIGZvciBKb2huIHRvIGNob29zZSBzdHJhdGVnaWMgcG9pbnRzIGZvciBoaXMgYXJteS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHNpbmdsZSBpbnRlZ2VyIFQgJm5kYXNoOyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBOIGFuZCBNIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gTiBpcyB0aGUgbnVtYmVyIG1lbnRpb25lZCBpbiB0aGUgZmlyc3QgcnVsZS4gTSBpcyB0aGUgbnVtYmVyIG9mIGxhdHRpY2UgcG9pbnRzIG9uIHRoZSB3b3JsZCBtYXAgYWxyZWFkeSBvY2N1cGllZCBieSBCcnVzJnJzcXVvO3MgYXJteS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIFg8c3ViPms8XC9zdWI+IGFuZCBZPHN1Yj5rPFwvc3ViPiBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIEVhY2ggbGF0dGljZSBwb2ludCAoWDxzdWI+azxcL3N1Yj4sIFk8c3ViPms8XC9zdWI+KSBpcyBvY2N1cGllZCBieSBCcnVzJnJzcXVvO3MgYXJteS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDc0LDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDcsPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBNICZsZTsgMjI1LDxcL2xpPlxyXG5cdDxsaT4tNyAmbGU7IFhrLCBZayAmbGU7IDcsPFwvbGk+XHJcblx0PGxpPmFsbCAoWGssIFlrKSB3aWxsIGJlIGRpc3RpbmN0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHdheXMgZm9yIEpvaG4gdG8gY2hvb3NlIHN0cmF0ZWdpYyBwb2ludHMgZm9yIGhpcyBhcm15LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d