시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWI4ZThcdWIyYzhcdWFjMDAgXHVjODA0XHViN2I1XHVjODEwXHVjNzQ0IFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzc0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBDb21wdXRlciBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Kb2huIGFuZCBCcnVzIGFyZSBwbGF5aW5nIGEgbWlsaXRhcnkgc3RyYXRlZ2ljIGdhbWUgb24gYSBQQy4gVGhlIGdhbWUgaXMgcGxheWVkIG9uIHRoZSBmbGF0IHdvcmxkIG1hcC4gQXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgZ2FtZSBCcnVzIHBsYWNlcyBoaXMgYXJteS4gVGhlbiBKb2huIGhhcyB0byBjaG9vc2Ugc3RyYXRlZ2ljIHBvaW50cyBmb3IgaGlzIGFybXkgYWNjb3JkaW5nIHRvIHRoZSBmb2xsb3dpbmcgcnVsZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+ZWFjaCBzdHJhdGVnaWMgcG9pbnQgbXVzdCBiZSBhIGxhdHRpY2UgcG9pbnQgKHgsIHkpIChhIGxhdHRpY2UgcG9pbnQgaXMgYSBwb2ludCB3aXRoIGludGVnZXIgY29vcmRpbmF0ZXMpIHN1Y2ggdGhhdCB8eHwgKyB8eXwgJmx0OyBOOzxcL2xpPlxyXG5cdDxsaT5Kb2huIGNhbiBjaG9vc2UgYW55IHBvc2l0aXZlIG51bWJlciBvZiBzdHJhdGVnaWMgcG9pbnRzOzxcL2xpPlxyXG5cdDxsaT5hbGwgdGhlIHN0cmF0ZWdpYyBwb2ludHMgbXVzdCBiZSBkaXN0aW5jdDs8XC9saT5cclxuXHQ8bGk+ZWFjaCBvZiB0aGUgc3RyYXRlZ2ljIHBvaW50cyBtdXN0IGJlIGZyZWUgKGkuZS4gbm90IG9jY3VwaWVkIGJ5IEJydXMmcnNxdW87cyBhcm15KTs8XC9saT5cclxuXHQ8bGk+ZWFjaCBwYWlyIG9mIGRpZmZlcmVudCBzdHJhdGVnaWMgcG9pbnRzIG11c3QgYmUgY29ubmVjdGVkIChwb3NzaWJseSB2aWEgc29tZSBvdGhlciBzdHJhdGVnaWMgcG9pbnRzKS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5IZXJlIHR3byBkaWZmZXJlbnQgbGF0dGljZSBwb2ludHMgKHgxLCB5MSkgYW5kICh4MiwgeTIpIGFyZSBjb25uZWN0ZWQgaWYgfHgxICZuZGFzaDsgeDJ8ICsgfHkxICZuZGFzaDsgeTJ8ID0gMS4gSWYgQSwgQiBhbmQgQyBhcmUgc3RyYXRlZ2ljIHBvaW50cywgQSBhbmQgQiBhcmUgY29ubmVjdGVkLCBCIGFuZCBDIGFyZSBjb25uZWN0ZWQsIHRoZW4gQSBhbmQgQyBhcmUgYWxzbyBjb25uZWN0ZWQuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBmaW5kIHRoZSBudW1iZXIgb2Ygd2F5cyBmb3IgSm9obiB0byBjaG9vc2Ugc3RyYXRlZ2ljIHBvaW50cyBmb3IgaGlzIGFybXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBzaW5nbGUgaW50ZWdlciBUICZuZGFzaDsgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgTiBhbmQgTSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIE4gaXMgdGhlIG51bWJlciBtZW50aW9uZWQgaW4gdGhlIGZpcnN0IHJ1bGUuIE0gaXMgdGhlIG51bWJlciBvZiBsYXR0aWNlIHBvaW50cyBvbiB0aGUgd29ybGQgbWFwIGFscmVhZHkgb2NjdXBpZWQgYnkgQnJ1cyZyc3F1bztzIGFybXkuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBYPHN1Yj5rPFwvc3ViPiBhbmQgWTxzdWI+azxcL3N1Yj4gc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBFYWNoIGxhdHRpY2UgcG9pbnQgKFg8c3ViPms8XC9zdWI+LCBZPHN1Yj5rPFwvc3ViPikgaXMgb2NjdXBpZWQgYnkgQnJ1cyZyc3F1bztzIGFybXkuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyA3NCw8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyA3LDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTSAmbGU7IDIyNSw8XC9saT5cclxuXHQ8bGk+LTcgJmxlOyBYaywgWWsgJmxlOyA3LDxcL2xpPlxyXG5cdDxsaT5hbGwgKFhrLCBZaykgd2lsbCBiZSBkaXN0aW5jdC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiB3YXlzIGZvciBKb2huIHRvIGNob29zZSBzdHJhdGVnaWMgcG9pbnRzIGZvciBoaXMgYXJteS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=