Mosquito, You Are Mine

Time limit2sMemory limit256 MB

Summary

Cover as many of up to 32 points as possible with one circle of the given diameter and report the maximum count.

Level: Medium6 of 10
Topics: Geometry, Brute force
Solved: No attempts yet

Problem

The mosquitoes are back this year. They ruined your picnic, and now it is your turn to strike back. You have no gear that keeps these pests away. All you own is the round empty bowl that held the potato salad. Looking down at the picnic table, you see mosquitoes sitting still, waiting for your guard to drop. Your chance to fight back is right now.

Find the largest number of mosquitoes you can trap by turning the bowl over and slamming it down on the table. You are given the diameter of the bowl and the exact coordinates of every mosquito. A mosquito is infinitely small, so it is a single point, and a mosquito lying on the rim of the bowl counts as trapped.

Input

The first line holds the number of trapping scenarios $n$ ( $1 \le n \le 100$ ). A blank line comes before each scenario. Each scenario starts with an integer $m$ ( $1 \le m \le 32$ ), the number of mosquitoes, and a real number $d$ ( $0 < d \le 200$ ), the diameter of the bowl. The next $m$ lines each hold the coordinates of one mosquito as real numbers $x$ , $y$ ( $-100 \le x, y \le 100$ ).

Output

For each scenario, print on one line the largest number of mosquitoes you can trap at once. Every input keeps the same answer when the diameter of the bowl grows by $10^{-5}$ .

Examples4

Example 1

Input

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

Expected output

3
4

Example 2
Input
```
1

1 0.5
-100.0 100.0
```
Expected output
```
1
```
Example 3
Input
```
1

3 2.0
0.0 0.0
2.0 0.0
5.0 5.0
```
Expected output
```
2
```

Example 4

Input

1

6 2.02
1.0 0.0
0.5 0.866025
-0.5 0.866025
-1.0 0.0
-0.5 -0.866025
0.5 -0.866025

Expected output