Space

Time limit1sMemory limit128 MB

Summary

Count, for each test case, the pairs of up to 100000 points whose Euclidean distance is strictly less than d.

Level: Medium5 of 10
Topics: Hash map, Geometry
Solved: No attempts yet

Problem

Teams at a programming contest cannot sit close to one another, because a team could copy the solution of the team next to it. You are given the position of every team and the minimum Euclidean distance $d$ required between two teams. Count the pairs of teams that sit too close to each other.

Two teams sit too close when the Euclidean distance between them is smaller than $d$ . A pair at distance exactly $d$ does not count.

Input

The first line contains one integer $t$ ( $1 \le t \le 100$ ), the number of test cases. Each test case is given as follows.

One line with two integers $n$ ( $1 \le n \le 100000$ ) and $d$ ( $1 \le d \le 50$ ), the number of teams and the minimum distance between two teams.
$n$ lines with two integers $x_i$ ( $0 \le x_i \le 1000000000$ ) and $y_i$ ( $0 \le y_i \le 1000000000$ ), the coordinates of the $i$ -th team. No two teams share the same coordinates.

Output

For each test case, print one line with the number of pairs of teams that sit too close to each other.

Examples1

Example 1
Input
```
1
6 3
0 0
0 3
2 1
2 3
3 0
3 1
```
Expected output
```
8
```