Nearby Gravitation

Time limit5sMemory limit128 MB

Summary

Count pairs of 3D points whose Euclidean distance is smaller than k for each test case.

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

Problem

In a system as crowded as the solar system, nobody wants to compute the gravity between two objects that sit very far apart, and the value comes out so small that the work is wasted anyway. So only pairs of objects closer than $k$ are worth looking at.

Given $n$ points in space, how many pairs of points are at a distance smaller than $k$ ?

Input

The input holds several test cases.

The first line of each test case has the number of points $n$ and the largest allowed distance $k$ . ( $2 \le n \le 100{,}000$ , $1 \le k \le 10^9$ )

Each of the next $n$ lines has three integers $x$ , $y$ , $z$ , the coordinates of one point. ( $-10^9 \le x, y, z \le 10^9$ )

No point is given twice within one test case, and at most $100{,}000$ pairs of points are at a distance of $k$ or less.

The last line of the input has two zeros, and that line is not a test case.

Output

For each test case print the number of point pairs whose distance is smaller than $k$ , one count per line.

Examples1

Example 1

Input

7 2
0 0 0
1 0 0
1 2 0
1 2 3
1000 1000 1000
1001 1001 1000
1001 999 1001
7 3
0 0 0
1 0 0
1 2 0
1 2 3
-1000 1000 -1000
-1001 1001 -1000
-1001 999 -1001
7 4
0 0 0
1 0 0
1 2 0
1 2 3
1000 -1000 1000
1001 -1001 1000
1001 -999 1001
0 0

Expected output

3
6
9