Lanterns

Hansel and Gretel's parents want to take them for a walk through the forest at night. Family hikes are a cherished tradition, but the children walk more slowly than their parents and are frightened by the predators that lurk in the dark, so they are not looking forward to this walk.

Having no way to navigate at night, Hansel and Gretel prepare by carrying lanterns into the forest during the day and attaching them to trees. At night, each lantern lights a circular spot of radius r centered on its tree (shadows are ignored). The children stay safe as long as they remain inside the lit area. If two lanterns are attached to trees that sit close enough to each other, their light spots touch or overlap and merge into a single connected light zone spanning several trees, within which the children can move safely.

First, Hansel and Gretel want to know how many trees can be illuminated together in one connected light zone: the maximum number of trees in a single connected zone when a lantern is attached to every tree. If this largest zone contains more than one tree, it is unique.

They could attach a lantern to every tree in that zone, but if two trees are very close, one tree's light spot may already illuminate the other, so fewer lanterns might be enough. To reduce weight, light pollution, and CO2, they also want the smallest number of lanterns that still illuminates every tree in the largest zone while keeping the lit area connected, so that any tree can be reached from any other without stepping into the dark (see Figure 1).

Figure 1: Two possible tree layouts. On the left, at most three trees can share one light zone, and a single well-placed lantern illuminates all three. On the right, at most four trees can share a zone, and two lanterns placed on the right pair of trees illuminate them most efficiently. In both layouts, one tree is too far from the others to join their zone.

• The first line contains an integer n (0 < n ≤ 100), the number of test cases.
• Each test case consists of:
  • A line with an integer r (0 < r ≤ 100), the radius of the circular light spot produced by a lantern.
  • A line with an integer t (1 < t ≤ 20), the number of trees in the forest.
  • t lines, each giving a tree's location as two integers x and y (integer coordinates).

For each test case, print one line with two integers separated by a single space. The first integer is the size of the largest connected light zone (the number of trees it illuminates). The second integer is the minimum number of lanterns needed to illuminate every tree in that zone while keeping the lit area connected.