Problem 1033. -- Stars

1033: Stars

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 2  Solved: 1
[Submit][Status][Web Board]

Description

话说立哥在经历了五次轰轰烈烈的恋爱失败以后,终于对现实生活充满了绝望,开始将目光投向网络。经过一番苦苦寻觅再狂轰滥炸之后,他终于网恋成功,如愿以偿得到了他的Julia。
对于这场来之不易的爱情,立哥可谓是小心谨慎、苦心经营,答应对方的事都全力以赴做到,决不让对方失望,真不愧是男人的典范!不过,这天立哥遇到了小小的麻烦……
原来,Julia在看完某日韩肥皂剧之后,进入了XX状态,竟然要求立哥把天上的星星捉下来送给她。这可难坏了立哥。大家也知道,天上那些小星星其实都是外太空的庞大天体,这怎么可能拿得到地球上来嘛!而且还要立哥用“捉”这么优雅的动作。
不过,立哥对爱情的执着感动了著名的爱神丘比特,他决定用神的力量帮立哥一把。这天晚上,他给立哥飞鸽传书:我送你一个脸盆。表面上这是一个脸盆,其实它是一面镜子。你只要先选择天上一个星星比较集中的区域,让它映在脸盆上,然后你大叫一声“挂!”,镜子中所有的星星都会被捕捉下来,并且只保持你看到它们的大小。不过,这个东西在用过一次之后就会失去法力,变成一个普通的脸盆了,所以你要尽量选择星星比较集中区域,才能捕捉到尽可能多的星星,祝你好运!
当晚立哥就在自己床底下发现一个奇怪的脸盆。
立哥看着这个脸盆,它可以反映(reflect)出天上半径为R的一个圆形区域;再看看天上,星星分布很不均匀。他想起了丘比特的话:一定要用脸盆捉下最多的星星。于是他再次找到参加ACM集训的你,希望你能帮助他确定天空中最合适的一片区域。
例如下面的情况(其中黑点表示星星),最多可以得到10颗星星,被圈起来的区域就是一个可行的方案。

注意:本问题中,那些在圆圈上的点也视为处于区域内。

Input

第1行只包含一个整数T(0<T≤10),表示一共有T组测试数据。
接下来为T组测试数据,一组结束以后紧接着从下一行开始就是下一组数据。
每组数据的第一行包含两个整数N,R(0≤N≤100,0≤R≤10000)。表示天上一共有N颗星星,脸盆可以反映天空中半径为R的圆形区域。
然后是N行,每行包含两个整数x,y,分别表示各颗星星在天上的坐标(-10000≤x,y≤10000)。

Output

共T行,每行对应一组测试数据的答案(将第I组测试数据的答案输出在第I行)。
每组测试数据的答案只包含一个整数,为立哥最多可捉到的星星数量。

Sample Input

3
2 3
0 0
5 0
3 5
0 0
8 0
8 6
9 14
24 42
56 40
60 41
51 44
44 44
20 46
48 49
28 54
59 55

Sample Output

2
3
6

HINT

Source

[Submit][Status]