시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 88 14 13 15.294%

문제

모기들이 올 해에도 돌아왔습니다! 그들은 당신의 소풍 계획을 완벽하게 망쳐놓았고, 이번에는 당신이 복수를 할 차례입니다. 안타깝게도 당신은 이 해충들을 잘 피할 수 있을 정도의 장비가 없습니다. 당신이 가진 것은 감자 샐러드를 담던 동그랗고 빈 그릇 뿐이지요. 소풍 테이블을 내려다 보자, 그 곳에는 당신의 방어가 허술해질 틈만을 기다리며 가만히 앉아있는 모기들이 보입니다. 당신이 맞서 싸울 기회는 바로 지금입니다.

당신은 그릇을 뒤집어 재빨리 테이블 위에 엎었을 때 가둘 수 있는 모기의 최대 숫자를 알고 싶습니다. 당신에게는 그릇의 지름과 각각 모기의 정확한 좌표가 주어집니다. 모기는 무한하게 작아서 한 점으로 표현될 수 있고, 그릇의 경계에 놓여진 모기 또한 가둬진 것으로 생각합니다.

입력

입력에 주어지는 첫 번째 숫자는 모기를 가두는 시나리오의 가지수 n (1 <= n <= 100)을 나타냅니다. 각각의 시나리오 전에는 하나의 공백줄이 주어집니다. 그 뒤에는 정수 m(1 <= m <= 32, 모기의 숫자)와 실수 d(0 < d <= 200, 그릇의 지름) 이 주어집니다. 이어지는 m 개의 줄에 걸쳐 모기들의 좌표가 실수 x, y(-100 <= x, y <= 100) 형태로 주어집니다.

출력

각각의 시나리오에 대하여 한 줄에 걸쳐 잡을 수 있는 최대 모기의 마릿수를 출력합니다. 입력들은 그릇의 지름이 10^(-5) 만큼 커져도 답은 같다는 것을 보장합니다.

예제 입력 1

2

4 1.5
1.0 3.75
3.0 1.0
1.0 2.25
1.5 3.0

8 3.0
-1.0 3.0
-1.0 2.0
-2.0 1.0
0.0 1.0
1.0 0.0
1.0 -1.0
2.0 -2.0
3.0 -1.0

예제 출력 1

3
4
W3sicHJvYmxlbV9pZCI6IjEwNDc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYWE4XHVhZTMwIFx1YjEwYyBcdWIwYjRcdWFlYmNcdWM1N2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmFhOFx1YWUzMFx1YjRlNFx1Yzc3NCBcdWM2MmMgXHVkNTc0XHVjNWQwXHViM2M0IFx1YjNjY1x1YzU0NFx1YzY1NFx1YzJiNVx1YjJjOFx1YjJlNCEgXHVhZGY4XHViNGU0XHVjNzQwIFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWMxOGNcdWQ0OGQgXHVhY2M0XHVkNjhkXHVjNzQ0IFx1YzY0NFx1YmNiZFx1ZDU1OFx1YWM4YyBcdWI5ZGRcdWNjZDBcdWIxOTNcdWM1NThcdWFjZTAsIFx1Yzc3NFx1YmM4OFx1YzVkMFx1YjI5NCBcdWIyZjlcdWMyZTBcdWM3NzQgXHViY2Y1XHVjMjE4XHViOTdjIFx1ZDU2MCBcdWNjMjhcdWI4NDBcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YzU0OFx1ZDBjMFx1YWU1ZFx1YWM4Y1x1YjNjNCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjNzc0IFx1ZDU3NFx1Y2RhOVx1YjRlNFx1Yzc0NCBcdWM3OTggXHVkNTNjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVjODE1XHViM2M0XHVjNzU4IFx1YzdhNVx1YmU0NFx1YWMwMCBcdWM1YzZcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWFjMDBcdWM5YzQgXHVhYzgzXHVjNzQwIFx1YWMxMFx1Yzc5MCBcdWMwZDBcdWI3ZWNcdWI0ZGNcdWI5N2MgXHViMmY0XHViMzU4IFx1YjNkOVx1YWRmOFx1Yjc5N1x1YWNlMCBcdWJlNDggXHVhZGY4XHViOTg3IFx1YmZkMFx1Yzc3NFx1YzljMFx1YzY5NC4gXHVjMThjXHVkNDhkIFx1ZDE0Y1x1Yzc3NFx1YmUxNFx1Yzc0NCBcdWIwYjRcdWI4MjRcdWIyZTQgXHViY2Y0XHVjNzkwLCBcdWFkZjggXHVhY2YzXHVjNWQwXHViMjk0IFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWJjMjlcdWM1YjRcdWFjMDAgXHVkNWM4XHVjMjIwXHVkNTc0XHVjOWM4IFx1ZDJjOFx1YjljY1x1Yzc0NCBcdWFlMzBcdWIyZTRcdWI5YWNcdWJhNzAgXHVhYzAwXHViOWNjXHVkNzg4IFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjI5NCBcdWJhYThcdWFlMzBcdWI0ZTRcdWM3NzQgXHViY2Y0XHVjNzg1XHViMmM4XHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NzQgXHViOWRlXHVjMTFjIFx1YzJmOFx1YzZiOCBcdWFlMzBcdWQ2OGNcdWIyOTQgXHViYzE0XHViODVjIFx1YzljMFx1YWUwOFx1Yzc4NVx1YjJjOFx1YjJlNC5cclxuPFwvcD5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YWRmOFx1Yjk4N1x1Yzc0NCBcdWI0YTRcdWM5ZDFcdWM1YjQgXHVjN2FjXHViZTY4XHViOWFjIFx1ZDE0Y1x1Yzc3NFx1YmUxNCBcdWM3MDRcdWM1ZDAgXHVjNWNlXHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWFjMDBcdWI0NTggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWFlMzBcdWM3NTggXHVjZDVjXHViMzAwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjMmY2XHVjMmI1XHViMmM4XHViMmU0LiBcdWIyZjlcdWMyZTBcdWM1ZDBcdWFjOGNcdWIyOTQgXHVhZGY4XHViOTg3XHVjNzU4IFx1YzljMFx1Yjk4NFx1YWNmYyBcdWFjMDFcdWFjMDEgXHViYWE4XHVhZTMwXHVjNzU4IFx1YzgxNVx1ZDY1NVx1ZDU1YyBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWJhYThcdWFlMzBcdWIyOTQgXHViYjM0XHVkNTVjXHVkNTU4XHVhYzhjIFx1Yzc5MVx1YzU0NFx1YzExYyBcdWQ1NWMgXHVjODEwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFkZjhcdWI5ODdcdWM3NTggXHVhY2JkXHVhY2M0XHVjNWQwIFx1YjE5M1x1YzVlY1x1YzljNCBcdWJhYThcdWFlMzAgXHViNjEwXHVkNTVjIFx1YWMwMFx1YjQ2Y1x1YzljNCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTY5XHViMmM4XHViMmU0LlxyXG48XC9wPiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJhYThcdWFlMzBcdWI5N2MgXHVhYzAwXHViNDUwXHViMjk0IFx1YzJkY1x1YjA5OFx1YjlhY1x1YzYyNFx1Yzc1OCBcdWFjMDBcdWM5YzBcdWMyMTggbiAoMSAmbHQ7PSBuICZsdDs9IDEwMClcdWM3NDQgXHViMDk4XHVkMGMwXHViMGM1XHViMmM4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0IFx1YzgwNFx1YzVkMFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2Y1XHViYzMxXHVjOTA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVhZGY4IFx1YjRhNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggbSgxICZsdDs9IG0gJmx0Oz0gMzIsIFx1YmFhOFx1YWUzMFx1Yzc1OCBcdWMyMmJcdWM3OTApXHVjNjQwIFx1YzJlNFx1YzIxOCBkKDAgJmx0OyBkICZsdDs9IDIwMCwgXHVhZGY4XHViOTg3XHVjNzU4IFx1YzljMFx1Yjk4NCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IG0gXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViYWE4XHVhZTMwXHViNGU0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMyZTRcdWMyMTggeCwgeSgtMTAwICZsdDs9IHgsIHkgJmx0Oz0gMTAwKSBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LlxyXG48XC9wPiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjRcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWJhYThcdWFlMzBcdWM3NTggXHViOWM4XHViOWJmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVjNzg1XHViODI1XHViNGU0XHVjNzQwIFx1YWRmOFx1Yjk4N1x1Yzc1OCBcdWM5YzBcdWI5ODRcdWM3NzQgMTBeKC01KSBcdWI5Y2NcdWQwN2MgXHVjZWU0XHVjODM4XHViM2M0IFx1YjJmNVx1Yzc0MCBcdWFjMTlcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmNmNFx1YzdhNVx1ZDU2OVx1YjJjOFx1YjJlNC5cclxuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQ3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBlc2t5IE1vc3F1aXRvZXMiLCJkZXNjcmlwdGlvbiI6IjxwPk1vc3F1aXRvZXMgYXJlIHJlbGVudGxlc3MgdGhpcyB0aW1lIG9mIHllYXIhIFRoZXkgaGF2ZSBhYnNvbHV0ZWx5IHJ1aW5lZCB5b3VyIGF0dGVtcHQgYXQgYSBwaWNuaWMgYW5kIGl0IGlzIHRpbWUgdG8gdGFrZSB5b3VyIHJldmVuZ2UuIFVuZm9ydHVuYXRlbHksIHlvdSBhcmUgbm90IHdlbGwgZXF1aXBwZWQgdG8gd2FyZCBvZmYgdGhlc2UgcGVzdHMuIEFsbCB5b3UgaGF2ZSBnb3QgYXQgeW91ciBkaXNwb3NhbCBpcyBhbiBlbXB0eSBib3dsIHRoYXQgcHJldmlvdXNseSBoZWxkIHBvdGF0byBzYWxhZC4gQXMgeW91IGdsYW5jZSBkb3duIGF0IHRoZSBwaWNuaWMgdGFibGUsIHlvdSBzZWUgYSBudW1iZXIgb2YgbW9zcXVpdG9lcyB3YWl0aW5nIGlkbHkgZm9yIHlvdSB0byBsZXQgeW91ciBndWFyZCBkb3duLiBUaGlzIGlzIHlvdXIgY2hhbmNlIHRvIGZpZ2h0IGJhY2suPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIG1vc3F1aXRvZXMgdGhhdCBjYW4gYmUgdHJhcHBlZCBieSBxdWlja2x5IGJyaW5naW5nIGRvd24gdGhlIGludmVydGVkIGJvd2wgb250byB0aGUgdGFibGUuIFlvdSB3aWxsIGJlIHByb3ZpZGVkIHdpdGggdGhlIGRpYW1ldGVyIG9mIHRoZSBib3dsIGFuZCB0aGUgZXhhY3QgbG9jYXRpb24gb2YgZWFjaCBtb3NxdWl0byBvbiB0aGUgdGFibGUuIEluIHRoaXMgZXhlcmNpc2UgeW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgbW9zcXVpdG9lcyBhcmUgaW5jcmVkaWJseSBzbWFsbCBhbmQgY2FuIHNpbXBseSBiZSBtb2RlbGVkIGFzIGEgcG9pbnQuIEEgbW9zcXVpdG8gdGhhdCBsaWVzIGV4YWN0bHkgdW5kZXIgdGhlIGVkZ2Ugb2YgdGhlIGJvd2wgaXMgY29uc2lkZXJlZCB0cmFwcGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IG51bWJlciBpbiB0aGUgaW5wdXQgd2lsbCBiZSBhbiBpbnRlZ2VyIDEgJmxlOyBuICZsZTsgMTAwIHRoYXQgZGVub3RlcyB0aGUgbnVtYmVyIG9mIG1vc3F1aXRvdHJhcHBpbmcgc2NlbmFyaW9zIHRoYXQgZm9sbG93LiBBIGJsYW5rIGxpbmUgY29tZXMgYXQgdGhlIGJlZ2lubmluZyBvZiBlYWNoIHNjZW5hcmlvLiBUaGVuIGZvbGxvd3MgYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciAxICZsZTsgbSAmbGU7IDMyICh0aGUgbnVtYmVyIG9mIG1vc3F1aXRvZXMpIGFuZCBhIHJlYWwgbnVtYmVyIDAgJmx0OyBkICZsZTsgMjAwICh0aGUgZGlhbWV0ZXIgb2YgdGhlIGJvd2wpLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbSBsaW5lcyB3aWxsIHNwZWNpZnkgdGhlIGxvY2F0aW9uIG9mIGEgbW9zcXVpdG8gaW4gdGhlIGZvcm0gb2YgcmVhbCBjb29yZGluYXRlcyAmbWludXM7MTAwICZsZTsgeCAmbGU7IDEwMCBhbmQgJm1pbnVzOzEwMCAmbGU7IHkgJmxlOyAxMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggc2NlbmFyaW8sIHlvdSBhcmUgdG8gcHJpbnQgdGhlIG1heGltdW0gbnVtYmVyIG9mIG1vc3F1aXRvZXMgdGhhdCBjYW4gYmUgY2F1Z2h0IHVuZGVyIHRoZSBib3dsIGluIHRoYXQgc2NlbmFyaW8uIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGFuc3dlciB3b3VsZCBub3QgY2hhbmdlIGlmIHRoZSBkaWFtZXRlciBvZiB0aGUgYm93bCBpcyBpbmNyZWFzZWQgYnkgYXQgbW9zdCAxMDxzdXA+LTU8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==