Description

Previous episode: 12155

After the "blackhole" incident, scientists accidentally found the potential energy of blackholes that created by the collision of multiple cat-toasts: the energy productivity of cat-toast blackhole is far more larger than cat-toasts.

By observing the cat-toast blackhole near the event horizon, they found that the collided cat-toasts weren't teared into slices but spinning around the blackhole. The scientists decided to call it "Nyan Cat". The Nyan Cat blackhole soon be wildly spread to the whole world.

Nyan Cat spinning around the blackhole

Recently, the scientists found that if there are too many Nyan Cat spinning around one blackhole, the huge angular momentum will form an unstable energy field, which would cause the Nyan Cat blackhole system crash, then all the nearby substance will be inhaled.

They soon set up a team to deal with the potential threat. If a cat-toast blackhole contains too many Nyan Cat spinning around it, they'll use catnip(貓薄荷) to lure it out.

You are in a power plant, whose energy source is the cat-toast blackhole. The power plant engineer gives you the original cat-toast location before they collide into a blackhole. You need to figure out the number of blackholes that is safety, and the number of blackholes that contains too many Nyan Cat.

---

There are $n$ nodes on an 2D-plane. If the distance of two nodes are equal to or closer than $r$, they are in the same group.

You are given a number $k$. You have to find out:

1. The number of groups with size less than $k$.
2. The number of groups with size equal to or greater than $k$.

• Note that the distance between two nodes $i$ and $j$ is:

  $$\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$$

  where $(x_i,y_i)$ and $(x_j,y_j)$ are the coordinate of the two nodes, respectively.

Input

The first line contains an integer $t$, indicates the number of testcases.

In each testcase:

• The first line contains $n$, $r$, and $k$.
• There are $n$ lines below. The $i$-th line of the $n$ lines contains the coordinate of $i$-th node: $(x_i,y_i)$.

$1\le t\le 100, 1\le k\le n\le 500, 1\le r\le 10^4$.

$-10^4\le x_i,y_i\le 10^4\ \forall\ i$.

 

Output

Output two numbers:

The number of groups with size less than $k$ ,and the number of groups with size equal to or greater than $k$, seperate with a space.

Remember to print a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss