Space

Time Limit: 50000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2366
64-bit integer IO format: %I64d      Java class name: Main

Description

During a programming contest, teams cannot sit close to each other, because then a team might copy the solution of another team. You are given the locations of the teams and the minimum required Euclidian distance between two teams. You have to find the number of pairs of teams that sit too close to each other.

Input

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 100 000) and d (1 <= d <= 50): the number of teams and the minimum distance between two teams.

n lines with two integers xi (0 <= xi <= 1 000 000 000) and yi (0 <= yi <= 1 000 000 000): the coordinates of the i-th team. No two teams will have the same coordinates.

Output

For each test case:

One line with the number of pairs of teams that sit too close to each other.

Sample Input

1
6 3
0 0
0 3
2 1
2 3
3 0
3 1

Sample Output

8

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .