Counting Neighbors

Input

The first line contains a single integer $t$ (1 \le t \le 10^4)—the number of test cases.

The first line of each test case contains two integers $n$ and $d$ (1 \le n \le 10^5, 1 \le d \le 3)—the number of people and the distance threshold.

Each of the next $n$ lines contains two integers x_i and y_i (-10^9 \le x_i, y_i \le 10^9)—the coordinates of the $i$-th person.

It is guaranteed that the sum of $n$ over all test cases does not exceed 10^5.

It is guaranteed that all points are pairwise distinct.

Output

Print $n$ integers in a single line. The $i$-th integer should represent the number of people (excluding the person themself) whose Manhattan distance from the $i$-th person is less than or equal to $d$.

Examples

Note

Consider the first test case:

1. Point $(1,1)$. There are exactly $3$ points considered neighbors: $(1,3)$, $(3,1)$, $(2,2)$.

2. Point $(1,3)$. There are exactly $3$ points considered neighbors: $(1,1)$, $(3,3)$, $(2,2)$.

3. Point $(3,1)$. There are exactly $3$ points considered neighbors: $(1,1)$, $(3,3)$, $(2,2)$.

4. Point $(3,3)$. There are exactly $3$ points considered neighbors: $(1,3)$, $(3,1)$, $(2,2)$.

5. Point $(2,2)$. There are exactly $4$ points considered neighbors: $(3,3)$, $(1,1)$, $(1,3)$, $(3,1)$.

All of them have a distance of at most d = 2.

Scoring

1. Subtask $1$ ($5$ points): 1 \le n \le 10

2. Subtask $2$ ($10$ points): 1 \le n \le 1000

3. Subtask $3$ ($10$ points): d = 1

4. Subtask $4$ ($15$ points): -1000 \le x_i, y_i \le 1000

5. Subtask $5$ ($60$ points): No additional constraints.