시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIE1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IE5cdWM3NzRcdWFjZTAsIE1cdWM3NDAgXHVjZTU4XHVjYzI4XHViOWFjXHVkMWEwXHVhYzAwIFx1YmMzMFx1Y2U1OFx1ZDU1YyBcdWFkNzBcdWIzMDBcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZTU4XHVjYzI4XHViOWFjXHVkMWEwXHVhYzAwIFx1YmMzMFx1Y2U1OFx1ZDU1YyBcdWFkNzBcdWIzMDBcdWM3NTggXHVjODhjXHVkNDVjIChYaywgWWspXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjQ1MCBcdWMyMThcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDc0LDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDcsPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBNICZsZTsgMjI1LDxcL2xpPlxyXG5cdDxsaT4tNyAmbGU7IFhrLCBZayAmbGU7IDcsPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCAoWGssIFlrKSBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YjhlOFx1YjJjOFx1YWMwMCBcdWM4MDRcdWI3YjVcdWM4MTBcdWM3NDQgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzQzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIENvbXB1dGVyIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkpvaG4gYW5kIEJydXMgYXJlIHBsYXlpbmcgYSBtaWxpdGFyeSBzdHJhdGVnaWMgZ2FtZSBvbiBhIFBDLiBUaGUgZ2FtZSBpcyBwbGF5ZWQgb24gdGhlIGZsYXQgd29ybGQgbWFwLiBBdCB0aGUgYmVnaW5uaW5nIG9mIHRoZSBnYW1lIEJydXMgcGxhY2VzIGhpcyBhcm15LiBUaGVuIEpvaG4gaGFzIHRvIGNob29zZSBzdHJhdGVnaWMgcG9pbnRzIGZvciBoaXMgYXJteSBhY2NvcmRpbmcgdG8gdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5lYWNoIHN0cmF0ZWdpYyBwb2ludCBtdXN0IGJlIGEgbGF0dGljZSBwb2ludCAoeCwgeSkgKGEgbGF0dGljZSBwb2ludCBpcyBhIHBvaW50IHdpdGggaW50ZWdlciBjb29yZGluYXRlcykgc3VjaCB0aGF0IHx4fCArIHx5fCAmbHQ7IE47PFwvbGk+XHJcblx0PGxpPkpvaG4gY2FuIGNob29zZSBhbnkgcG9zaXRpdmUgbnVtYmVyIG9mIHN0cmF0ZWdpYyBwb2ludHM7PFwvbGk+XHJcblx0PGxpPmFsbCB0aGUgc3RyYXRlZ2ljIHBvaW50cyBtdXN0IGJlIGRpc3RpbmN0OzxcL2xpPlxyXG5cdDxsaT5lYWNoIG9mIHRoZSBzdHJhdGVnaWMgcG9pbnRzIG11c3QgYmUgZnJlZSAoaS5lLiBub3Qgb2NjdXBpZWQgYnkgQnJ1cyZyc3F1bztzIGFybXkpOzxcL2xpPlxyXG5cdDxsaT5lYWNoIHBhaXIgb2YgZGlmZmVyZW50IHN0cmF0ZWdpYyBwb2ludHMgbXVzdCBiZSBjb25uZWN0ZWQgKHBvc3NpYmx5IHZpYSBzb21lIG90aGVyIHN0cmF0ZWdpYyBwb2ludHMpLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkhlcmUgdHdvIGRpZmZlcmVudCBsYXR0aWNlIHBvaW50cyAoeDEsIHkxKSBhbmQgKHgyLCB5MikgYXJlIGNvbm5lY3RlZCBpZiB8eDEgJm5kYXNoOyB4MnwgKyB8eTEgJm5kYXNoOyB5MnwgPSAxLiBJZiBBLCBCIGFuZCBDIGFyZSBzdHJhdGVnaWMgcG9pbnRzLCBBIGFuZCBCIGFyZSBjb25uZWN0ZWQsIEIgYW5kIEMgYXJlIGNvbm5lY3RlZCwgdGhlbiBBIGFuZCBDIGFyZSBhbHNvIGNvbm5lY3RlZC48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIG51bWJlciBvZiB3YXlzIGZvciBKb2huIHRvIGNob29zZSBzdHJhdGVnaWMgcG9pbnRzIGZvciBoaXMgYXJteS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHNpbmdsZSBpbnRlZ2VyIFQgJm5kYXNoOyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBOIGFuZCBNIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gTiBpcyB0aGUgbnVtYmVyIG1lbnRpb25lZCBpbiB0aGUgZmlyc3QgcnVsZS4gTSBpcyB0aGUgbnVtYmVyIG9mIGxhdHRpY2UgcG9pbnRzIG9uIHRoZSB3b3JsZCBtYXAgYWxyZWFkeSBvY2N1cGllZCBieSBCcnVzJnJzcXVvO3MgYXJteS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIFg8c3ViPms8XC9zdWI+IGFuZCBZPHN1Yj5rPFwvc3ViPiBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIEVhY2ggbGF0dGljZSBwb2ludCAoWDxzdWI+azxcL3N1Yj4sIFk8c3ViPms8XC9zdWI+KSBpcyBvY2N1cGllZCBieSBCcnVzJnJzcXVvO3MgYXJteS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDc0LDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDcsPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBNICZsZTsgMjI1LDxcL2xpPlxyXG5cdDxsaT4tNyAmbGU7IFhrLCBZayAmbGU7IDcsPFwvbGk+XHJcblx0PGxpPmFsbCAoWGssIFlrKSB3aWxsIGJlIGRpc3RpbmN0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHdheXMgZm9yIEpvaG4gdG8gY2hvb3NlIHN0cmF0ZWdpYyBwb2ludHMgZm9yIGhpcyBhcm15LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==