You have $n$ distinct points $(x_1, y_1),\ldots,(x_n,y_n)$ on the plane and a non-negative integer parameter $k$. Each point is a microscopic steel ball and $k$ is the attract power of a ball when it's charged. The attract power is the same for all balls.

In one operation, you can select a ball $i$ to charge it. Once charged, all balls with Manhattan distance at most $k$ from ball $i$ move to the position of ball $i$. Many balls may have the same coordinate after an operation.

More formally, for all balls $j$ such that $|x_i - x_j| + |y_i - y_j| \le k$, we assign $x_j:=x_i$ and $y_j:=y_i$.

An example of an operation. After charging the ball in the center, two other balls move to its position. On the right side, the red dot in the center is the common position of those balls.

Your task is to find the minimum number of operations to move all balls to the same position, or report that this is impossible.


-----Input-----

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

The first line of each test case contains two integers $n$, $k$ ($2 \le n \le 100$, $0 \le k \le 10^6$) — the number of balls and the attract power of all balls, respectively.

The following $n$ lines describe the balls' coordinates. The $i$-th of these lines contains two integers $x_i$, $y_i$ ($0 \le x_i, y_i \le 10^5$) — the coordinates of the $i$-th ball.

It is guaranteed that all points are distinct.


-----Output-----

For each test case print a single integer — the minimum number of operations to move all balls to the same position, or $-1$ if it is impossible.


-----Examples-----

Input
3
3 2
0 0
3 3
1 1
3 3
6 7
8 8
6 9
4 1
0 0
0 1
0 2
0 3
Output
-1
1
-1


-----Note-----

In the first test case, there are three balls at $(0, 0)$, $(3, 3)$, and $(1, 1)$ and the attract power is $2$. It is possible to move two balls together with one operation, but not all three balls together with any number of operations.

In the second test case, there are three balls at $(6, 7)$, $(8, 8)$, and $(6, 9)$ and the attract power is $3$. If we charge any ball, the other two will move to the same position, so we only require one operation.

In the third test case, there are four balls at $(0, 0)$, $(0, 1)$, $(0, 2)$, and $(0, 3)$, and the attract power is $1$. We can show that it is impossible to move all balls to the same position with a sequence of operations.

Source: codeforces | Difficulty: EASY
Tags: Geometry

Complete search

Greedy algorithms


Solutions:
ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
for _ in range(t()):
	(n, k) = ll()
	l = []
	for _ in range(n):
		l.append(list(ll()))
	for i in range(n):
		f = 1
		for j in range(n):
			if abs(l[j][0] - l[i][0]) + abs(l[j][1] - l[i][1]) > k:
				f = -1
				break
		if f == 1:
			print(1)
			break
	else:
		print(-1)


def ball_list(amount):
	l = []
	l1 = []
	for a in range(amount):
		l.append([int(x) for x in input().split()])
		l1.append(sum(l[a]))
	return (l, l1)

def close(l, power):
	for i in l:
		true = False
		for a in l:
			if abs(i[0] - a[0]) + abs(i[1] - a[1]) > power:
				true = True
				break
		if true == False:
			return True
	return False
for i in range(int(input())):
	(balls, power) = [int(x) for x in input().split()]
	(l, l1) = ball_list(balls)
	l2 = list(sorted(l1))
	if close(l, power):
		print(1)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ali = []
	for i in range(n):
		li = list(map(int, input().split()))
		ali.append(li)
	for i in range(0, n):
		f = 0
		for j in range(n):
			q = abs(ali[i][0] - ali[j][0])
			w = abs(ali[i][1] - ali[j][1])
			if q + w > k:
				f = 1
				break
		if f == 0:
			break
	if f == 1:
		print(-1)
	else:
		print(1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = []
	ans = -1
	for i in range(n):
		li.append(list(map(int, input().split())))
	for i in range(n):
		ok = True
		for j in range(n):
			if i != j and k < abs(li[i][0] - li[j][0]) + abs(li[i][1] - li[j][1]):
				ok = False
				break
		if ok:
			ans = 1
			break
	print(ans)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	points = []
	for i in range(n):
		point = [int(x) for x in input().split(' ')]
		points.append(point)
	flm = 0
	for i in range(len(points)):
		fl = 1
		for j in range(len(points)):
			if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) > k:
				fl = 0
				break
		if fl:
			flm = 1
			break
	if flm:
		print(1)
	else:
		print(-1)


for i in range(int(input())):
	a = [int(j) for j in input().split()]
	n = a[0]
	k = a[1]
	x = []
	y = []
	s = 0
	for i in range(n):
		a = [int(j) for j in input().split()]
		x.append(a[0])
		y.append(a[1])
	for i in range(n):
		j = 0
		while j < n:
			if abs(x[i] - x[j]) + abs(y[i] - y[j]) > k:
				break
			j += 1
		if j == n:
			s = 1
			break
	if s == 1:
		print(1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ball = list()
	for _ in range(n):
		(x, y) = map(int, input().split())
		ball.append((x, y))
	for i in ball:
		flag = 0
		for j in ball:
			if abs(i[0] - j[0]) + abs(i[1] - j[1]) > k:
				flag = 1
				break
			else:
				pass
		if flag == 1:
			ans = -1
		if flag == 0:
			ans = 1
			break
	print(ans)


t = int(input())
for j in range(0, t):
	(n, k) = map(int, input().split())
	x = []
	y = []
	for i in range(0, n):
		(a, b) = (0, 0)
		(a, b) = map(int, input().split())
		x.append(a)
		y.append(b)
	fl = 0
	for i in range(0, n):
		fl = -1
		for g in range(0, n):
			if abs(x[i] - x[g]) + abs(y[i] - y[g]) <= k:
				fl = 0
			else:
				fl = -1
				break
		if fl == 0:
			break
	if fl == -1:
		print(-1)
	else:
		print(1)


for _ in ' ' * int(input()):
	(n, k) = map(int, input().split())
	cnt = 0
	val = []
	for i in range(n):
		val.append(list(map(int, input().split())))
	for i in range(n):
		f = 0
		for j in range(n):
			if i != j:
				if abs(val[i][0] - val[j][0]) + abs(val[i][1] - val[j][1]) > k:
					f = 1
					break
		if f == 0:
			cnt = 1
			break
	if cnt == 0:
		print(-1)
	else:
		print(1)


remaing_test_cases = int(input())
while remaing_test_cases > 0:
	(points_count, K) = map(int, input().split())
	points = []
	for i in range(points_count):
		(x, y) = map(int, input().split())
		points.append([x, y])
	flag = 0
	for i in range(points_count):
		count_power = 0
		for j in range(points_count):
			if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) <= K:
				count_power = count_power + 1
		if count_power == points_count:
			print(1)
			flag = 1
			break
	if flag == 0:
		print(-1)
	remaing_test_cases = remaing_test_cases - 1


t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	a = []
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		a.append((x, y))
	flag = False
	for i in range(n):
		tmp = set([1 if abs(a[j][0] - a[i][0]) + abs(a[j][1] - a[i][1]) <= k else 0 for j in range(n)])
		if 0 not in tmp:
			flag = True
			break
	if flag:
		print(1)
	else:
		print(-1)
	t -= 1


import math
i1 = int(input())
for z in range(i1):
	i = [int(a) for a in input().split()]
	t = []
	a1 = 0
	for x in range(i[0]):
		t1 = [int(a) for a in input().split()]
		t.append(t1)
	for x in t:
		s = 0
		for z in t:
			if math.fabs(x[0] - z[0]) + math.fabs(x[1] - z[1]) > i[1]:
				s = 1
			if s == 1:
				break
		if s == 0:
			a1 = 1
			print(1)
			break
	if a1 == 0:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	loc = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		loc.append([x, y])
	ans = -1
	i = 0
	while i < n and ans == -1:
		for j in range(n):
			if abs(loc[i][0] - loc[j][0]) + abs(loc[i][1] - loc[j][1]) > k:
				break
			if j == n - 1:
				ans = 1
		i += 1
	print(ans)


test = int(input())

def dist(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])
for t in range(test):
	(n, k) = map(int, input().split())
	P = [list(map(int, input().split())) for i in range(n)]
	found = None
	for i in range(n):
		found = True
		for j in range(n):
			if i == j:
				continue
			elif dist(P[i], P[j]) > k:
				found = False
				break
		if found:
			break
	if found:
		print(1)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	XY = []
	for i in range(n):
		(x, y) = map(int, input().split())
		XY.append((x, y))
	flag = False
	for i in range(n):
		(xi, yi) = XY[i]
		for j in range(n):
			(xj, yj) = XY[j]
			if abs(xi - xj) + abs(yi - yj) > k:
				break
		else:
			flag = True
			break
	if flag:
		print(1)
	else:
		print(-1)


import sys, os
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
MOD = 10 ** 9 + 7

def f(a, b, x, y, k):
	return abs(x - a) + abs(y - b) <= k

def main():
	ans = []
	for _ in range(int(input())):
		(n, k) = read()
		arr = []
		for i in range(n):
			arr.append(read())
		for i in arr:
			(a, b) = i
			fl = 1
			for j in arr:
				(x, y) = j
				fl &= f(a, b, x, y, k)
			if fl:
				ans.append(1)
				break
		if not fl:
			ans.append(-1)
	print('\n'.join(map(str, ans)))
main()


from os import path
import sys
from math import ceil, floor, gcd, log
from collections import defaultdict, Counter
maxx = float('inf')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	I = lambda : int(sys.stdin.buffer.readline())
	tup = lambda : map(int, sys.stdin.buffer.readline().split())
	lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
	S = lambda : sys.stdin.readline().replace('\n', '').strip()
	stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
	star = lambda x: print(' '.join(map(str, x)))
else:
	I = lambda : int(sys.stdin.buffer.readline())
	tup = lambda : map(int, sys.stdin.buffer.readline().split())
	lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
	S = lambda : sys.stdin.readline().replace('\n', '').strip()
	stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
	star = lambda x: print(' '.join(map(str, x)))
for _ in range(I()):
	(n, k) = tup()
	a = []
	for i in range(n):
		(b, c) = tup()
		a.append((b, c))
	ans = maxx
	for i in range(n):
		se = set()
		f = 1
		for j in range(n):
			if i != j:
				ana = abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1])
				if ana <= k:
					se.add(ana)
				else:
					f = 0
					break
		if f:
			ans = min(ans, len(se))
			se.clear()
		else:
			se.clear()
	if ans == maxx:
		print(-1)
	else:
		print(1)


import sys
from math import gcd, ceil, sqrt, ceil
from math import gcd, ceil, floor, sqrt, copysign, factorial, fmod, fsum, degrees
from math import expm1, exp, log, log2, acos, asin, cos, tan, sin, pi, e, tau, inf, nan, atan2
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7
from collections import Counter, defaultdict as df
from functools import reduce

def counter(l):
	return dict(Counter(l))

def printm(l):
	for i in range(len(l[0])):
		print(*l[i])

def P(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True
import math

def lcm(a, b):
	return int(a * b / gcd(a, b))

def so(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

def rev(l):
	return list(reversed(l))

def ini():
	return int(sys.stdin.readline())

def inp():
	return map(int, sys.stdin.readline().strip().split())

def li():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()

def inputm(n, m):
	return [li() for i in range(n)]

def d(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def solve():
	(n, k) = inp()
	l = []
	for i in range(n):
		l += [li()]
	c = 0
	t = 0
	for i in l:
		c = 0
		for j in l:
			if d(i[0], i[1], j[0], j[1]) <= k:
				c += 1
		if c == n:
			t = 1
			break
	if t:
		print(1)
	else:
		print(-1)
for i in range(ini()):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	B = []
	for m in range(n):
		A = list(map(int, input().split()))
		B.append(A)
	ans = -1
	for i in range(n):
		for j in range(n):
			x = abs(B[i][0] - B[j][0])
			y = abs(B[i][1] - B[j][1])
			if x + y <= k:
				ans = 1
			else:
				ans = -1
				break
		if ans == 1:
			break
	print(ans)


def dist(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve(n, k, p):
	for i in range(n):
		if all((dist(p[i], p[j]) <= k for j in range(n))):
			return 1
	return -1
tests = int(input())
for test in range(tests):
	(n, k) = map(int, input().split())
	p = [list(map(int, input().split())) for i in range(n)]
	print(solve(n, k, p))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	s = True
	for i in range(n):
		p = True
		for j in range(n):
			if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) > k:
				p = False
				break
		if p:
			print(1)
			s = False
			break
	if s:
		print(-1)


t = int(input())
ans = []
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	values = []
	for _ in range(n):
		values.append(list(map(int, input().split())))
	found = False
	for i in range(n):
		okay = True
		vals = [values[i][0], values[i][1]]
		for j in range(n):
			if i == j:
				continue
			if abs(values[j][0] - vals[0]) + abs(values[j][1] - vals[1]) > k:
				okay = False
				break
		if okay:
			found = True
			break
	if found:
		ans.append('1')
	else:
		ans.append('-1')
print('\n'.join(ans))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append((x, y))
	ans = -2
	f = 0
	for i in range(n):
		flag = 0
		for j in range(n):
			if abs(a[j][0] - a[i][0]) + abs(a[j][1] - a[i][1]) <= k:
				continue
			else:
				flag = 1
				break
		if flag == 0:
			f = 1
			break
	if f == 1:
		print(1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	for i in range(n):
		s = 0
		x = l[i][0]
		y = l[i][1]
		for j in range(n):
			if abs(x - l[j][0]) + abs(y - l[j][1]) <= k:
				pass
			else:
				break
		else:
			print(1)
			break
	else:
		print(-1)


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, K, balls):
	for (x1, y1) in balls:
		bad = False
		for (x2, y2) in balls:
			if x1 == x2 and y1 == y2:
				continue
			if abs(x1 - x2) + abs(y1 - y2) > K:
				bad = True
				break
		if not bad:
			return 1
	return -1
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, K) = [int(x) for x in input().split()]
	balls = [[int(x) for x in input().split()] for i in range(N)]
	ans = solve(N, K, balls)
	print(ans)


t = int(input())
while t:
	t = t - 1
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append([x, y])
	flag = True
	for i in range(n):
		c = 0
		for j in range(n):
			if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) <= k:
				c += 1
			else:
				break
		if c == n:
			flag = False
			break
	if flag:
		print(-1)
	else:
		print(1)


t = int(input())
while t:
	t -= 1
	(n, k) = list(map(int, input().split()))
	points = []
	for _ in range(n):
		points.append(list(map(int, input().split())))
	for point in points:
		ans = 1
		for opoint in points:
			if point != opoint and abs(point[0] - opoint[0]) + abs(point[1] - opoint[1]) > k:
				ans = -1
		if ans == 1:
			print(1)
			break
	else:
		print(-1)


def dis(x, y, x1, y1):
	return abs(x - x1) + abs(y - y1)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = []
	for i in range(n):
		p = list(map(int, input().split()))
		li.append(p)
	count = 0
	for i in range(n):
		flag = False
		for j in range(n):
			if i != j:
				val = dis(li[i][0], li[i][1], li[j][0], li[j][1])
				if val > k:
					flag = True
					break
		if not flag:
			break
	if flag:
		print(-1)
	elif li.count(li[0]) == n:
		print(0)
	else:
		print(1)


import sys
input = sys.stdin.readline
import math
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	points = []
	for i in range(n):
		points.append(tuple(map(int, input().split())))
	adj = dict()
	for i in range(n):
		for j in range(i + 1, n):
			temp1 = points[i]
			temp2 = points[j]
			if abs(temp1[0] - temp2[0]) + abs(temp1[1] - temp2[1]) <= k:
				if temp1 not in adj:
					adj[temp1] = 0
				if temp2 not in adj:
					adj[temp2] = 0
				adj[temp1] += 1
				adj[temp2] += 1
	ans = False
	for key in adj:
		if adj[key] == n - 1:
			ans = True
	if ans:
		print(1)
	else:
		print(-1)


import math

def getint():
	return [int(i) for i in input().split()]

def getstr():
	return [str(i) for i in input().split()]

def solve():
	m = []
	(n, k) = getint()
	for i in range(n):
		m.append(getint())
	flag = 1
	for i in range(n):
		for j in range(n):
			if abs(m[i][0] - m[j][0]) + abs(m[i][1] - m[j][1]) > k:
				flag = 0
				break
		else:
			flag = 1
			break
	if flag == 0:
		print(-1)
	else:
		print(1)
for _ in range(int(input())):
	solve()


t = int(input())
rs = []
for z in range(t):
	nk = input()
	(n, k) = nk.split(' ')
	(n, k) = (int(n), int(k))
	cor = []
	for i in range(n):
		c = input()
		(x, y) = c.split(' ')
		(x, y) = (int(x), int(y))
		cor.append([x, y])
	ok = True
	for i in range(n):
		ok = True
		for j in range(n):
			if abs(cor[i][0] - cor[j][0]) + abs(cor[i][1] - cor[j][1]) > k:
				ok = False
				break
		if ok:
			rs.append(1)
			break
	if not ok:
		rs.append(-1)
for item in rs:
	print(item)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = []
	for i in range(n):
		p.append([int(x) for x in input().split()])
	c = 1
	ans = -1
	for i in range(n):
		c = 1
		for j in range(n):
			if i != j and abs(p[j][0] - p[i][0]) + abs(p[j][1] - p[i][1]) > k:
				c = 0
				break
		if c == 1:
			ans = 1
			break
	print(ans)


import math

def dist(p1, p2):
	(x1, y1) = (p1[0], p1[1])
	(x2, y2) = (p2[0], p2[1])
	d = abs(x1 - x2) + abs(y1 - y2)
	return d
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		(i, j) = map(int, input().split())
		l.append([i, j])
	for i in range(n):
		flage = True
		for j in range(0, n):
			if dist(l[i], l[j]) > k:
				flage = False
				break
		if flage:
			break
	if flage:
		print(1)
	else:
		print(-1)


for ii in range(int(input())):
	(x, y) = map(int, input().split())
	(a, f) = ([], True)
	for jj in range(x):
		a.append(list(map(int, input().split())))
	for jj in range(x):
		c = 0
		for kk in range(x):
			if abs(a[jj][0] - a[kk][0]) + abs(a[jj][1] - a[kk][1]) <= y:
				c += 1
			else:
				break
		if c == x:
			print(1)
			f = False
			break
	if f:
		print(-1)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = []
	yes = 1
	for i in range(n):
		a.append(list(map(int, input().split())))
	for i in range(n):
		yes = 0
		for r in range(n):
			if abs(a[i][0] - a[r][0]) + abs(a[i][1] - a[r][1]) > k:
				yes = 1
		if yes == 0:
			break
	if yes == 0:
		print(1)
	else:
		print(-1)


def balls_of_steel(n, k, balls):
	current_index = 0
	while current_index < len(balls):
		compare = balls[current_index]
		terminate = 1
		for (i, j) in balls:
			ans = abs(compare[0] - i) + abs(compare[1] - j)
			if ans > k:
				terminate = 0
				break
		if terminate == 0:
			current_index += 1
		else:
			return 1
	return -1
test = int(input())
for y in range(test):
	(n, k) = list(map(int, input().split()))
	balls = []
	for x in range(n):
		q = list(map(int, input().split()))
		balls.append(q)
	print(balls_of_steel(n, k, balls))


from collections import defaultdict
for t in range(int(input())):
	ball_idx = defaultdict(list)
	rang = defaultdict(list)
	(n, k) = map(int, input().split())
	listi = []
	for i in range(n):
		(x, y) = map(int, input().split())
		p = []
		p.append(x)
		p.append(y)
		listi.append(p)
	kam = False
	for i in listi:
		count = 0
		for j in listi:
			p = abs(i[0] - j[0])
			l = abs(i[1] - j[1])
			if 0 < p + l <= k:
				count += 1
		if count == n - 1:
			kam = True
			print(1)
			break
	if kam == False:
		print(-1)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = []
	for i in range(n):
		x = list(map(int, input().split()))
		l.append(x)
	for i in l:
		c = 1
		for j in l:
			if abs(i[0] - j[0]) + abs(i[1] - j[1]) > k:
				c = 0
				break
		if c == 1:
			print(1)
			break
	if c == 0:
		print(-1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	lst = []
	for j in range(n):
		lst1 = list(map(int, input().split(' ')))
		lst.append(lst1)
	for i in range(n):
		count = 0
		for j in range(n):
			if i == j:
				continue
			if abs(abs(lst[i][0] - lst[j][0]) + abs(lst[i][1] - lst[j][1])) <= k:
				count += 1
			elif count == n - 1:
				break
			else:
				break
		if count == n - 1:
			break
	if count == n - 1:
		print(1)
	else:
		print(-1)


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations

def main():
	(n, k) = map(int, input().split())
	ptr = []
	for i in range(n):
		ptr.append(tuple(map(int, input().split())))
	for i in range(n):
		ok = True
		for j in range(n):
			if abs(ptr[i][0] - ptr[j][0]) + abs(ptr[i][1] - ptr[j][1]) > k:
				ok = False
		if ok:
			print(1)
			return
	print(-1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


T = int(input())
for i in range(T):
	(N, K) = list(map(int, input().split()))
	C = []
	for j in range(N):
		(X, Y) = list(map(int, input().split()))
		C.append([X, Y])
	Check = False
	for j in range(N):
		for k in range(N):
			Part1 = C[j][0] - C[k][0]
			Part2 = C[j][1] - C[k][1]
			if Part1 < 0:
				Part1 = Part1 * -1
			if Part2 < 0:
				Part2 = Part2 * -1
			D = Part1 + Part2
			if D <= K:
				Check = True
			else:
				Check = False
				break
		if Check:
			break
	if Check == True:
		print(1)
	else:
		print(-1)


import sys
import math
input = sys.stdin.readline

def pi():
	return int(input())

def pl():
	return int(input(), 16)

def ti():
	return list(map(int, input().split()))

def ts():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	B()

def A():
	t = pi()
	while t:
		t -= 1
		n = ti()
		s = ts()
		temp = ''
		for c in s:
			if c == 'b':
				temp += 'b'
		ans = temp
		if len(temp) == 0:
			print(*s, sep='')
			continue
		for c in s:
			if c != 'b':
				ans += c
		print(ans)

def B():
	t = pi()
	while t:
		t -= 1
		[n, k] = ti()
		p = [[] * n] * n
		for i in range(n):
			p[i] = ti()
		isPossible = False
		for i in range(n):
			f = True
			for j in range(n):
				d = abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1])
				if d > k:
					f = False
					break
			if f:
				isPossible = True
		if not isPossible:
			print(-1)
		else:
			print(1)
main()


import math
import sys

class Read:

	@staticmethod
	def string():
		return input()

	@staticmethod
	def int():
		return int(input())

	@staticmethod
	def list(sep=' '):
		return input().split(sep)

	@staticmethod
	def list_int(sep=' '):
		return list(map(int, input().split(sep)))

def solve():
	(n, k) = Read.list_int()
	a = []
	for i in range(n):
		a.append(Read.list_int())
	for i in range(n):
		v = True
		for j in range(n):
			if i != j:
				if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) > k:
					v = False
					break
		if v:
			print(1)
			return
	print(-1)
query_count = Read.int()
while query_count:
	query_count -= 1
	solve()


import sys
T = int(input())
for t in range(T):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	points = []
	pathMap = [[False for i in range(n)] for j in range(n)]
	for p in range(n):
		(x, y) = list(map(int, sys.stdin.readline().split()))
		points.append((x, y))
	for i in range(n):
		ok = True
		pathMap[i][i] = True
		for j in range(i + 1, n):
			if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) <= k:
				pathMap[i][j] = True
				pathMap[j][i] = True
		if not any(pathMap[i]):
			ok = False
			break
	if not ok:
		print(-1)
	else:
		ok = False
		for i in range(n):
			if all(pathMap[i]):
				ok = True
				break
		print('{}'.format(1 if ok else -1))


I = lambda : tuple(map(int, input().split()))
for _ in range(int(input())):
	(n, ll) = map(int, input().split())
	p = []
	for i in range(n):
		p.append(I())
	for i in range(n):
		k = 0
		a = 1
		while k < n and a != 0:
			a = int(abs(p[i][0] - p[k][0]) + abs(p[i][1] - p[k][1]) <= ll)
			k = k + 1 * a
		if k == n:
			print(1)
			break
	if k != n:
		print(-1)


import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		xy = []
		for i in range(n):
			xy.append(list(map(int, input().split())))
		f = 0
		for i in range(n):
			currx = xy[i][0]
			curry = xy[i][1]
			f = 1
			for j in range(n):
				if abs(xy[j][0] - currx) + abs(xy[j][1] - curry) > k:
					f = 0
					break
			if f:
				break
		if f:
			print(1)
		else:
			print(-1)
	return
main()


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	lst = []
	for i in range(n):
		a = list(map(int, input().split()))
		lst.append(a)
	f = False
	for i in range(n):
		fnd = True
		for j in range(n):
			dis = abs(lst[i][0] - lst[j][0]) + abs(lst[i][1] - lst[j][1])
			if dis > k:
				fnd = False
				break
		if fnd == True:
			f = True
			break
	if f == True:
		print(1)
	else:
		print(-1)


def find():
	(N, K) = map(int, input().split())
	(minX, maxX, minY, maxY) = (10 ** 5, 0, 10 ** 5, 0)
	num = []
	for __ in range(N):
		(X, Y) = map(int, input().split())
		num.append((X, Y))
	for i in range(N):
		for j in range(N):
			if abs(num[i][0] - num[j][0]) + abs(num[i][1] - num[j][1]) > K:
				break
		else:
			return 1
	else:
		return -1
for _ in range(int(input())):
	print(find())


def f(n, k):
	pts = [list(map(int, input().split())) for _ in range(n)]
	deg = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			(a, b) = pts[i]
			(x, y) = pts[j]
			man = abs(x - a) + abs(y - b)
			if man <= k:
				deg[i] += 1
				deg[j] += 1
	if max(deg) == n - 1:
		return 1
	else:
		return -1
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	print(f(n, k))


from collections import deque
import sys

def input():
	return sys.stdin.readline().rstrip()
INF = 1 << 40

def solve():
	(n, k) = map(int, input().split())
	point = [tuple(map(int, input().split())) for i in range(n)]
	for i in range(n):
		(px, py) = point[i]
		if all((abs(px - x) + abs(py - y) <= k for (x, y) in point)):
			print(1)
			return
	print(-1)
	return

def main():
	t = 1
	t = int(input())
	for i in range(t):
		solve()
	return
main()


for _ in range(int(input())):
	(n, r) = [int(i) for i in input().split()]
	balls = []
	z = False
	for _ in range(n):
		balls.append([int(i) for i in input().split()])
	for i in balls:
		if max([abs(i[0] - j[0]) + abs(i[1] - j[1]) for j in balls]) <= r:
			print(1)
			z = True
			break
	if not z:
		print(-1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	t = -1
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	for i in l:
		q = 0
		for j in l:
			if abs(i[1] - j[1]) + abs(i[0] - j[0]) <= k:
				q += 1
			else:
				break
		if q == n:
			t = 1
	print(t)


from math import *

def toOneBall(n, k, a):
	for i in range(n):
		res = 0
		for j in range(n):
			if int(fabs(a[i][0] - a[j][0])) + int(fabs(a[i][1] - a[j][1])) > k:
				res += 1
				break
		if res == 0:
			return True
	return False
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = []
	for i in range(n):
		a.append([int(x) for x in input().split()])
	if toOneBall(n, k, a):
		print(1)
	else:
		print(-1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	(n, k) = RL()
	dic = [[] for _ in range(n)]
	p = []
	for _ in range(n):
		(x, y) = RL()
		p.append((x, y))
	for i in range(n - 1):
		for j in range(i + 1, n):
			if abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]) <= k:
				dic[i].append(j)
				dic[j].append(i)
	res = -1
	for i in range(n):
		if len(dic[i]) == n - 1:
			res = 1
			break
	print(res)


t = int(input())
for j in range(0, t):
	l1 = [int(c) for c in input().split()]
	n = l1[0]
	kd = l1[1]
	p = []
	for i in range(0, n):
		p.append([int(x) for x in input().split()])
	match = True
	for i in range(0, n):
		match = True
		for k in range(0, n):
			if abs(p[i][0] - p[k][0]) + abs(p[i][1] - p[k][1]) > kd:
				match = False
				break
		if match == True:
			break
	if match == True:
		print(1)
	else:
		print(-1)


import sys
from collections import *
import math
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	x = [0] * n
	y = [0] * n
	for i in range(n):
		(x[i], y[i]) = [int(x) for x in input().split()]
	for i in range(n):
		count = 0
		for j in range(n):
			if abs(x[i] - x[j]) + abs(y[i] - y[j]) <= k:
				count += 1
		if count == n:
			break
	if count == n:
		print(1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = list(map(int, input().strip().split()))
	poi = []
	for i in range(n):
		poi.append(list(map(int, input().strip().split())))
	for i in range(n):
		flag = True
		for j in range(n):
			if i == j:
				pass
			if abs(poi[i][0] - poi[j][0]) + abs(poi[i][1] - poi[j][1]) > k:
				flag = False
				break
		if flag:
			break
	if flag:
		print(1)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = [() for i in range(n)]
	for i in range(n):
		A[i] = tuple(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			if abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1]) > k:
				break
		else:
			print(1)
			break
	else:
		print(-1)


for u in range(int(input())):
	(n, k) = map(int, input().split())
	x = []
	for i in range(n):
		(a, b) = map(int, input().split())
		x.append([a, b])
	f = False
	ans = 0
	for i in range(len(x)):
		l = 0
		for j in range(len(x)):
			if abs(x[i][0] - x[j][0]) + abs(x[i][1] - x[j][1]) > k:
				break
			l += 1
		if l == n:
			ans = 1
			break
	if ans == 1:
		print(1)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr += [[x, y]]
	flag = -1
	for i in range(n):
		count = 0
		for j in range(n):
			if abs(arr[i][0] - arr[j][0]) + abs(arr[i][1] - arr[j][1]) <= k:
				count += 1
		if count == n:
			flag = 1
			break
	print(flag)


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	arr = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr.append((x, y))
	ok = False
	for i in range(n):
		(cx, cy) = arr[i]
		for j in range(n):
			if abs(cx - arr[j][0]) + abs(cy - arr[j][1]) > k:
				break
		else:
			ok = True
			break
	if ok:
		print(1)
		continue
	print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = [list(map(int, input().split())) for l in range(n)]
	t = 0
	for i in range(n):
		(x0, y0) = c[i]
		for j in range(n):
			(x1, y1) = c[j]
			if abs(x0 - x1) + abs(y0 - y1) > k:
				t = -1
				break
		else:
			t = 1
			break
	print(t)


def main(args):
	t = int(input())
	p = []
	ks = []
	for i in range(t):
		p.append([])
		ks.append(input().split(' '))
		n = int(ks[i][0])
		for j in range(n):
			p[i].append([])
			l = input().split(' ')
			p[i][j].append(int(l[0]))
			p[i][j].append(int(l[1]))
	for i in range(t):
		n = int(ks[i][0])
		k = int(ks[i][1])
		for j in range(n):
			counter = 0
			for m in range(n):
				if cityblock(p[i][j], p[i][m]) <= k:
					counter = counter + 1
			if counter == n:
				print(1)
				break
		if counter != n:
			print(-1)

def cityblock(p1, p2):
	return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
import sys
sys.exit(main(sys.argv))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	(a, f) = ([], 0)
	for i in range(n):
		a.append(tuple(map(int, input().split())))
	for i in range(n):
		f1 = 1
		for j in range(n):
			if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) > k:
				f1 = 0
				break
		if f1:
			f = 1
			break
	if f:
		print(1)
	else:
		print(-1)


def run():
	tests = int(input())
	for i in range(tests):
		(n, k) = tuple(map(int, input().split()))
		points = []
		for i in range(n):
			point = list(map(int, input().split()))
			points.append(point)
		minimum = balls_of_steel(points, n, k)
		print(minimum)

def balls_of_steel(points, n, k):
	for i in range(n):
		central_node = True
		for j in range(n):
			if manhattan_distance(points[i], points[j]) > k:
				central_node = False
				break
		if central_node == True:
			return 1
	return -1

def manhattan_distance(p1, p2):
	x_dist = abs(p1[0] - p2[0])
	y_dist = abs(p1[1] - p2[1])
	return x_dist + y_dist
run()


t = int(input())
while t > 0:
	count = -1
	l = []
	l1 = []
	(a, b) = map(int, input().split())
	for i in range(0, a, 1):
		(x, y) = map(int, input().split())
		l.append(x)
		l1.append(y)
	for i in range(0, a, 1):
		ok = True
		for j in range(0, a, 1):
			m = abs(l[i] - l[j]) + abs(l1[i] - l1[j])
			if m > b:
				ok = False
				break
		if ok:
			count = 1
			break
	print(count)
	t -= 1


import math
cases = int(input())
for _ in range(cases):
	(num, k) = map(int, input().split())
	coors = [list(map(int, input().split())) for _ in range(num)]
	for (cx, cy) in coors:
		valid = True
		for (x, y) in coors:
			d = abs(x - cx) + abs(y - cy)
			if d > k:
				valid = False
				break
		if valid:
			print(1)
			break
	else:
		print(-1)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for __ in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	c = 0
	cc = 0
	for i in range(n):
		c = 0
		for j in range(n):
			if i != j and abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1]) <= k:
				c += 1
		if c == n - 1:
			print(1)
			cc = 1
			break
	if cc != 1:
		print(-1)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = set()
	a = []
	for __ in range(n):
		(x, y) = map(int, input().split())
		a.append([x, y])
	for i in range(n):
		z = 0
		c = 0
		for j in range(n):
			if i != j:
				x = abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1])
				if x <= k:
					continue
				else:
					c += 1
					break
		if c == 0:
			print(1)
			break
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	ans = []
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	l1 = []
	for i in range(n):
		l1.append([])
		for j in range(i + 1, n):
			l1[i].append(abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1]))
		for j in range(0, i + 1):
			l1[i].append(abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1]))
	for i in range(n):
		c = 0
		for j in l1[i]:
			if j <= k:
				c += 1
		ans.append(c)
	if n in ans:
		print(1)
	else:
		print(-1)


from collections import defaultdict, deque
import sys
import bisect
input = sys.stdin.readline
t = int(input())
for ii in range(t):
	(n, k) = map(int, input().split())
	store = []
	for i in range(n):
		(x, y) = map(int, input().split())
		store.append((x, y))
	check = [0] * n
	for i in range(n):
		for j in range(n):
			if i != j:
				manhat = abs(store[i][0] - store[j][0]) + abs(store[i][1] - store[j][1])
				if manhat <= k:
					check[i] += 1
	if n - 1 in check:
		print(1)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = []
	y = []
	for _ in range(n):
		(a, b) = map(int, input().split())
		x.append(a)
		y.append(b)
	ans = -1
	for i in range(n):
		ok = True
		for j in range(n):
			d = abs(x[i] - x[j]) + abs(y[i] - y[j])
			if d > k:
				ok = False
				break
		if ok:
			ans = 1
			break
	print(ans)


from sys import stdin
ip = stdin.readline
for _ in range(int(ip())):
	(n, k) = map(int, ip().split())
	p = []
	for _ in range(n):
		p.append([*map(int, ip().split())])
	flag = False
	for i in range(n):
		(x1, y1) = p[i]
		f = True
		for j in range(n):
			if not j == i:
				(x2, y2) = p[j]
				power = abs(x1 - x2) + abs(y1 - y2)
				if power > k:
					f = False
					break
		if f:
			flag = True
			break
	print('1' if flag else '-1')


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	points = []
	for i in range(n):
		points.append([int(x) for x in input().split()])
	for i in range(len(points)):
		y = 0
		for j in range(len(points)):
			(a, b) = (points[i][0], points[i][1])
			(c, d) = (points[j][0], points[j][1])
			if abs(a - c) + abs(b - d) <= k:
				y += 1
			else:
				break
		if y == len(points):
			print(1)
			break
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = []
	chc = 0
	dis = 0
	for i in range(n):
		l1 = list(map(int, input().split()))
		l.append(l1)
	for i in range(0, n):
		for j in range(0, n):
			dis = abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1])
			if dis > k:
				chc = 1
				break
			else:
				chc = 0
		if chc == 0:
			break
	if chc == 0:
		print('1')
	else:
		print('-1')


def solve(n, k, points):
	for i in range(n):
		flag = 1
		for j in range(n):
			if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) > k:
				flag = 0
				break
		if flag == 1:
			return 1
	return -1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	points = []
	for i in range(n):
		(a, b) = map(int, input().split())
		points.append([a, b])
	print(solve(n, k, points))


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		(n, k) = get_ints()
		data = []
		for i in range(n):
			data.append(get_list())
		ans = -1
		for i in range(n):
			count = 0
			for j in range(n):
				if i != j:
					if abs(data[i][0] - data[j][0]) + abs(data[i][1] - data[j][1]) <= k:
						count += 1
			if count == n - 1:
				ans = 1
				break
		get_print_int(ans)
solve()


def check(ar, k):
	for i in range(len(ar)):
		c = 0
		x = ar[i][0]
		y = ar[i][1]
		for j in range(len(ar)):
			xx = ar[j][0]
			yy = ar[j][1]
			if abs(xx - x) + abs(yy - y) <= k:
				c += 1
			else:
				break
		if c == len(ar):
			return 1
	return -1
y122 = int(input())
for _ in range(y122):
	(n, k) = map(int, input().split())
	ar = []
	xl = 'xxx'
	xr = 'xxx'
	yl = 'xxx'
	yr = 'xxx'
	for i in range(n):
		ar.append(list(map(int, input().split())))
	print(check(ar, k))


R = lambda : [*map(int, input().split())]
exec(R()[0] * 'n,k=R();a=[R()for _ in[0]*n];print(+(min(max(abs(x-u)+abs(y-v)for x,y in a)for u,v in a)<=k)or-1);')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = []
	f = 0
	for i in range(n):
		l1.append([int(a) for a in input().split()])
	for i in range(n):
		f = 0
		for j in range(n):
			if abs(l1[i][0] - l1[j][0]) + abs(l1[i][1] - l1[j][1]) > k:
				f = 1
				break
		if f == 0:
			break
	if f:
		print(-1)
	else:
		print(1)


from collections import Counter

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

def manhattan_dist(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def solve(points, k):
	for p1 in points:
		found = True
		for p2 in points:
			if p1 == p2:
				continue
			if manhattan_dist(p1.x, p1.y, p2.x, p2.y) > k:
				found = False
				break
		if found:
			return 1
	return -1
for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	points = []
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		points.append(Point(x, y))
	print(solve(points, k))


t = int(input())
for t1 in range(t):
	(n, k) = map(int, input().split())
	x = []
	y = []
	for t2 in range(n):
		(x1, x2) = map(int, input().split())
		x.append(x1)
		y.append(x2)
	flag = 0
	for a in range(n):
		flag = 0
		for b in range(n):
			if a != b:
				if abs(x[a] - x[b]) + abs(y[a] - y[b]) > k:
					flag = 1
		if flag == 0:
			print(1)
			flag = 2
			break
	if flag != 2:
		print(-1)


from math import *
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
	f = 0
	for i in range(n):
		for j in range(n):
			m = abs(l[i][0] - l[j][0])
			p = abs(l[i][1] - l[j][1])
			if m + p > k:
				break
		else:
			print(1)
			f = 1
			break
	if f == 0:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		a.append([*map(int, input().split())])
	ok = False
	for i in range(n):
		if all((abs(a[i][0] - x) + abs(a[i][1] - y) <= k for [x, y] in a)):
			ok = True
	print([-1, 1][ok])


from collections import defaultdict
tcs = int(input())
for tc in range(tcs):
	(n, k) = list(map(int, input().split()))
	li = list()
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		li.append([x, y])
	ans = -1
	for i in range(n):
		flag = True
		for j in range(n):
			if i != j and k < abs(li[i][0] - li[j][0]) + abs(li[i][1] - li[j][1]):
				flag = False
				break
		if flag:
			ans = 1
			break
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	(x, y) = ([0] * n, [0] * n)
	for i in range(n):
		(x[i], y[i]) = map(int, input().split())
	ans = -1
	for i in range(n):
		for j in range(n):
			if abs(x[i] - x[j]) + abs(y[i] - y[j]) > k:
				break
			if j == n - 1:
				ans = 1
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	ans = -1
	for i in range(n):
		count = 0
		for j in range(n):
			if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) <= k:
				count += 1
		if count == n:
			ans = 1
			break
	print(ans)


t = int(input())
for i in range(t):
	(n1, k) = map(int, input().strip().split())
	l = []
	for i in range(n1):
		(x, y) = map(int, input().strip().split())
		l.append([x, y])
	flag = 0
	y = 0
	for j in l:
		flag = 0
		for m in l:
			s = abs(j[0] - m[0])
			s += abs(j[1] - m[1])
			if s > k:
				flag = 1
				break
		if flag == 0:
			y = 1
			break
	if y == 1:
		print('1')
	else:
		print('-1')


def dist(x, y):
	return sum((abs(x[i] - y[i]) for i in range(2)))
t = int(input())
for __ in range(t):
	(n, k) = map(int, input().split())
	ls = []
	for __ in range(n):
		ls.append(tuple(map(int, input().split())))
	ok = False
	for i in range(n):
		flag = False
		for j in range(n):
			if dist(ls[i], ls[j]) > k:
				flag = True
				break
		if not flag:
			ok = True
			break
	print(1 if ok else -1)


for tt in range(int(input())):
	(n, k) = map(int, input().split())
	p = []
	for i in range(n):
		p.append(list(map(int, input().split())))
	for i in range(n):
		b = True
		for j in range(n):
			if abs(p[i][1] - p[j][1]) + abs(p[i][0] - p[j][0]) > k:
				b = False
				break
		if b:
			break
	if b:
		print(1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	points = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		points.append((x, y))
	broken1 = False
	for i in range(n):
		(xi, yi) = points[i]
		broken = False
		for j in range(n):
			(xj, yj) = points[j]
			if abs(xi - xj) + abs(yi - yj) > k:
				broken = True
				break
		if not broken:
			print(1)
			broken1 = True
			break
	if not broken1:
		print(-1)


def dist(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	points = []
	for i in range(n):
		(x, y) = map(int, input().split())
		points.append([x, y])
	deg = []
	m = 0
	for i in range(n):
		d = 0
		for j in range(n):
			if dist(points[i], points[j]) <= k:
				d += 1
		m = max(m, d)
	if m < n:
		print(-1)
	else:
		print(1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort(key=lambda x: x[0] + x[1])
	f = 0
	for i in range(n):
		for j in range(n):
			x1 = l[i][0]
			y1 = l[i][1]
			x2 = l[j][0]
			y2 = l[j][1]
			d = abs(x1 - x2) + abs(y1 - y2)
			if d > k:
				f += 1
				break
	if f == n:
		print(-1)
	else:
		print(1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil, floor, sqrt
from collections import Counter, defaultdict, deque

def int1():
	return int(input())

def map1():
	return map(int, input().split())

def list1():
	return list(map(int, input().split()))
mod = pow(10, 9) + 7

def solve():
	(n, k) = map1()
	l1 = []
	d = defaultdict(list)
	for i in range(n):
		l1.append(list1())
	for i in range(n):
		c = 0
		for j in range(n):
			if i != j:
				v = abs(l1[i][0] - l1[j][0]) + abs(l1[i][1] - l1[j][1])
				if v <= k:
					c = c + 1
				else:
					c = 0
		if c == n - 1:
			print(1)
			return
	print(-1)
for _ in range(int(input())):
	solve()


import math
from functools import reduce

def readGenerator():
	while True:
		tokens = input().split(' ')
		for t in tokens:
			yield t
reader = readGenerator()

def readWord():
	return next(reader)

def readInt():
	return int(next(reader))

def readFloat():
	return float(next(reader))

def readLine():
	return input()

def solve(n, k, a):
	for i in range(n):
		for j in range(n):
			d = abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1])
			if d > k:
				break
		else:
			return 1
	return -1
t = readInt()
for _ in range(t):
	(n, k) = [readInt() for _ in range(2)]
	a = []
	for _ in range(n):
		a.append((readInt(), readInt()))
	print(solve(n, k, a))


for tc in range(int(input())):
	ball = []

	def f(a, b):
		return abs(ball[a][0] - ball[b][0]) + abs(ball[a][1] - ball[b][1])
	(n, k) = map(int, input().split())
	for i in range(n):
		ball.append(list(map(int, input().split())))
	for i in range(n):
		for j in range(n):
			if f(i, j) > k:
				break
		else:
			flag = True
			break
	else:
		flag = False
	if flag:
		print(1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = []
	for i in range(n):
		s.append(list(map(int, input().split())))
	for i in s:
		flag = 0
		for j in s:
			if abs(i[0] - j[0]) + abs(i[1] - j[1]) <= k:
				flag = 1
			else:
				flag = 0
				break
		if flag == 1:
			print(1)
			break
	if flag == 0:
		print(-1)


def distance(p1, p2):
	return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def balls_of_steel(P, n, k):
	for (i, p1) in enumerate(P):
		possible = True
		total_dist = 0
		for (j, p2) in enumerate(P):
			dist = distance(p1, p2)
			total_dist += dist
			if dist > k:
				possible = False
				break
		if possible:
			break
	if not possible:
		return -1
	else:
		return 1 if total_dist > 0 else 0
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	P = [[int(v) for v in input().split()] for _ in range(n)]
	ans = balls_of_steel(P, n, k)
	print(ans)


t = int(input())
for s in range(t):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	flag = 0
	for i in range(0, n):
		c = 0
		for j in range(0, n):
			if abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1]) > k:
				break
			c = c + 1
		if c == n:
			flag = 1
			print(1)
			break
	if flag == 0:
		print(-1)


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	XY = [list(map(int, input().split())) for _ in range(N)]
	for (cx, cy) in XY:
		f = True
		for (x, y) in XY:
			d = abs(cx - x) + abs(cy - y)
			if d > K:
				f = False
				break
		if f:
			print(1)
			break
	else:
		print(-1)


from sys import stdin, gettrace
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	(n, k) = map(int, inputi().split())
	points = []
	for _ in range(n):
		points.append(tuple(map(int, inputi().split())))
	dist = []
	for (px, py) in points:
		for (qx, qy) in points:
			if abs(px - qx) + abs(py - qy) > k:
				break
		else:
			print(1)
			return
	else:
		print(-1)

def main():
	t = int(inputi())
	for _ in range(t):
		solve()
main()


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	flag = 0
	for i in range(n):
		ans = 1
		for j in range(n):
			if i < n and j < n:
				temp = abs(arr[i][0] - arr[j][0]) + abs(arr[i][1] - arr[j][1])
				if temp > k:
					ans = 0
					break
		if ans == 1:
			flag = 1
			break
	if flag == 1:
		print(1)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	L = []
	for j in range(n):
		(x, y) = map(int, input().split())
		L.append([x, y])
	mn = 0
	ok = False
	for i in range(n):
		mn = 0
		for j in range(n):
			if i != j:
				x = abs(L[i][0] - L[j][0]) + abs(L[i][1] - L[j][1])
				mn = max(mn, x)
		if mn <= k:
			ok = True
	if ok == False:
		print(-1)
	else:
		print(1)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.append(list(map(int, input().split())))
	f = 1
	for i in range(n):
		f = 1
		for j in range(n):
			if abs(c[i][0] - c[j][0]) + abs(c[i][1] - c[j][1]) > k:
				f = -1
				break
		if f == 1:
			break
	print(f)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	lst = []
	for j in range(n):
		(x, y) = map(int, sys.stdin.readline().split())
		lst.append([x, y])
	for j in range(n):
		check = 1
		for l in range(n):
			if abs(lst[j][0] - lst[l][0]) + abs(lst[j][1] - lst[l][1]) > k:
				check = 0
				break
		if check:
			sys.stdout.write(str(1) + '\n')
			break
	if not check:
		sys.stdout.write(str(-1) + '\n')


def ass(a, b):
	if a != b:
		print(f'Assertion error: {a} != {b}')
	else:
		print('OK')

def number():
	return int(input())

def numbers():
	return [int(item) for item in input().split()]

def word():
	return input()

def words():
	return [item for item in input().split()]

def dump(lst):
	for (i, item) in enumerate(lst):
		print(i, item)

def binsearch(arr, a, b):
	m = (a + b) // 2
	if a >= b:
		return a - 1 if arr[a] == 0 else a
	return binsearch(arr, a, m - 1) if arr[m] == 0 else binsearch(arr, m + 1, b)

def f(k, balls):
	flag = 1
	for (x0, y0) in balls:
		for (x1, y1) in balls:
			if abs(x0 - x1) + abs(y0 - y1) > k:
				flag = -1
				break
		else:
			flag = 1
			break
	return flag
for t in range(number()):
	(n, k) = numbers()
	balls = [numbers() for i in range(n)]
	print(f(k, balls))


from collections import deque
sol = []
for test in range(int(input())):
	(n, k) = map(int, input().split())
	points = []
	for i in range(n):
		points.append(tuple(map(int, input().split())))
	invalid = True
	for i in range(n):
		can = True
		for j in range(n):
			if i == j:
				continue
			dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
			if dist > k:
				can = False
				break
		if can:
			invalid = False
			break
	if invalid:
		sol.append(-1)
	else:
		sol.append(1)
for r in sol:
	print(r)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		t = list(map(int, input().split()))
		l.append(t[:])
	ans = -1
	for i in range(n):
		t = 0
		for j in range(n):
			if abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1]) > k:
				t = -1
				break
		if t == 0:
			ans = 0
			break
	if ans == 0:
		print(1)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	li = []
	for j in range(n):
		li.append(list(map(int, input().split())))
	for j in range(n):
		c = 0
		x1 = li[j][0]
		y1 = li[j][1]
		for k1 in range(n):
			x2 = li[k1][0]
			y2 = li[k1][1]
			dist = abs(x1 - x2) + abs(y1 - y2)
			if dist > k:
				c = 1
				break
		if c == 0:
			print(1)
			break
	if c == 1:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	xs = []
	ys = []
	for ii in range(n):
		(x, y) = map(int, input().split())
		xs.append(x)
		ys.append(y)
	done = False
	for i in range(n):
		max_k = -1
		for j in range(n):
			max_k = max(max_k, abs(xs[i] - xs[j]) + abs(ys[i] - ys[j]))
		if max_k <= k:
			print(1)
			done = True
			break
	if not done:
		print(-1)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	mans = -1
	for i in range(n):
		ans = 1
		for j in range(n):
			if i != j and abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1]) > k:
				ans -= 1
				break
		if ans == 1:
			print(1)
			mans = 1
			break
	if mans == -1:
		print(-1)


import sys
input = sys.stdin.readline
line_inp = lambda : list(map(int, input().strip().split()))
int_inp = lambda : int(input())

def distance(x, y):
	return abs(x[0] - y[0]) + abs(x[1] - y[1])

def solve(n, k, points):
	man_dist = [0] * n
	for i in range(n):
		for j in range(n):
			dist = distance(points[i], points[j])
			if dist <= k:
				man_dist[i] += 1
		if man_dist[i] == n:
			return 1
	return -1
for i in range(int_inp()):
	(n, k) = line_inp()
	points = []
	for j in range(n):
		points.append(line_inp())
	print(solve(n, k, points))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = []
	y = []
	for i in range(n):
		(a, b) = map(int, input().split())
		x.append(a)
		y.append(b)
	comp = 0
	for i in range(n):
		flag = 1
		for j in range(n):
			if abs(x[i] - x[j]) + abs(y[i] - y[j]) > k:
				flag = 0
				break
		if flag == 1:
			comp = 1
			break
	if comp == 1:
		print(1)
	else:
		print(-1)


from math import *
from collections import deque
from copy import deepcopy
import sys

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def multi():
	return map(int, input().split())

def strmulti():
	return map(str, inp().split())

def lis():
	return list(map(int, inp().split()))

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def stringlis():
	return list(map(str, inp().split()))

def out(var):
	sys.stdout.write(str(var))

def printlist(a):
	print(' '.join((str(a[i]) for i in range(len(a)))))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
t = int(inp())
for _ in range(t):
	(n, k) = multi()
	a = []
	for i in range(n):
		a.append(lis())
	ans = -1
	num = 0
	for i in range(n):
		already = True
		for j in range(n):
			if i == j:
				continue
			if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) > k:
				already = False
				break
		if already:
			ans = 1
			break
	print(ans)


def canCollapse(balls, k):
	if len(balls) <= 1:
		return True
	for a in balls:
		found = 0
		for b in balls:
			if abs(a[0] - b[0]) + abs(a[1] - b[1]) <= k:
				found += 1
		if found <= 1:
			return False
		if found == len(balls):
			return True
	return False
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	balls = []
	for j in range(n):
		balls.append(list(map(int, input().split(' '))))
	print(1 if canCollapse(balls, k) else -1)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = []
	s = 0
	for i in range(n):
		a.append(list(map(int, input().split())))
	for x in a:
		for y in a:
			if abs(x[0] - y[0]) + abs(x[1] - y[1]) > k:
				s += 1
				break
	if s < n:
		print(1)
	else:
		print(-1)


BUFSIZE = 8192
import os
import sys
import math
from io import BytesIO, IOBase
from bisect import bisect_left
from bisect import bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(tuple(map(int, input().split())))
		f = 0
		c = -1
	for i in range(n):
		f = 0
		for j in range(n):
			if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) <= m:
				f += 1
		if f == n:
			c = 1
			break
	print(c)


for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	p = [tuple(map(int, input().split())) for i in range(0, n)]
	if any([all([abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]) <= k for j in range(0, n)]) for i in range(0, n)]):
		print(1)
	else:
		print(-1)


import sys
input = lambda : sys.stdin.readline().rstrip()
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	X = []
	for _ in range(N):
		(x, y) = map(int, input().split())
		X.append((x, y))
	for (i, (x, y)) in enumerate(X):
		for (j, (x2, y2)) in enumerate(X):
			if abs(x - x2) + abs(y - y2) > K:
				break
		else:
			print(1)
			break
	else:
		print(-1)


from sys import stdin
cas = int(stdin.readline().strip())
for ca in range(cas):
	(n, k) = map(int, stdin.readline().strip().split())
	s = [list(map(int, stdin.readline().strip().split())) for i in range(n)]
	f1 = True
	for i in range(n):
		f = True
		for j in range(n):
			if abs(s[i][0] - s[j][0]) + abs(s[i][1] - s[j][1]) > k:
				f = False
				break
		if f:
			print(1)
			f1 = False
			break
	if f1:
		print(-1)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = []
	for j in range(n):
		a.append(list(map(int, input().split())))
	c = 0
	for j in range(n):
		p = 0
		for k in range(n):
			if abs(a[j][0] - a[k][0]) + abs(a[j][1] - a[k][1]) <= m:
				p += 1
		if p == n:
			c = 1
	if c == 1:
		print('1')
	else:
		print('-1')


for i in range(int(input())):
	result = False
	(n, k) = map(int, input().split())
	balls = []
	for j in range(n):
		balls.append(tuple(map(int, input().split())))
	for ball in balls:
		for j in range(n):
			if abs(ball[0] - balls[j][0]) + abs(ball[1] - balls[j][1]) > k:
				break
		else:
			result = True
	print(1 if result else -1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	flag = 1
	for i in range(n):
		l.append(list(map(int, input().split())))
	for (x1, y1) in l:
		for (x2, y2) in l:
			if abs(x1 - x2) + abs(y1 - y2) > k:
				flag = -1
				break
		else:
			flag = 1
			break
	print(flag)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [0] * n
	for i in range(n):
		a[i] = tuple(map(int, input().split()))
	d = [0] * n
	for i in range(n - 1):
		for j in range(i + 1, n):
			dist = abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1])
			if dist <= k:
				d[i] += 1
				d[j] += 1
	if n - 1 in d:
		print(1)
	else:
		print(-1)


t = int(input())

def dist(x1, x2, y1, y2):
	return abs(x1 - x2) + abs(y1 - y2)
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = []
	for i in range(n):
		(x, y) = map(int, input().split())
		nums.append([x, y])
	ans = -1
	for i in range(n):
		mx = 0
		for j in range(n):
			mx = max(mx, dist(nums[i][0], nums[j][0], nums[i][1], nums[j][1]))
		if mx <= k:
			ans = 1
	print(ans)


import math
from collections import defaultdict
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	mat = []
	for i in range(n):
		lis = list(map(int, input().split()))
		mat.append(lis)
	lim = len(mat)
	f = 0
	for i in range(lim):
		c = 0
		for j in range(lim):
			ch = abs(mat[i][0] - mat[j][0]) + abs(mat[i][1] - mat[j][1])
			if ch <= k:
				c += 1
		if c == n:
			f = 1
			break
	if f:
		print(1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = -1
	w = []
	for i in range(n):
		(x, y) = map(int, input().split())
		w.append((x, y))
	for i in range(n):
		b = 0
		for j in range(n):
			if abs(w[i][0] - w[j][0]) + abs(w[i][1] - w[j][1]) > k:
				b = 1
				break
		if b == 0:
			ans = 1
			break
	print(ans)


t = int(input())
while t > 0:
	ls = []
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	for i in range(x):
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		tup = (a, b)
		ls.append(tup)
	c = 0
	i = 0
	while i < x:
		j = 0
		while j < x:
			p = abs(ls[i][0] - ls[j][0]) + abs(ls[i][1] - ls[j][1])
			if p <= y:
				j = j + 1
				c = c + 1
			else:
				c = 0
				i = i + 1
				break
		if c > 0:
			break
	if c == 0:
		d = -1
	else:
		d = 1
	print(d)
	t = t - 1


for test in range(int(input())):
	(n, k) = list(map(int, input().split()))
	balls = []
	for i in range(n):
		balls.append(tuple(map(int, input().split())))
	balls.sort()
	found = False
	for c_ball in balls:
		ok = True
		for ball in balls:
			ok &= abs(c_ball[0] - ball[0]) + abs(c_ball[1] - ball[1]) <= k
		if ok:
			found = True
	if found:
		print(1)
	else:
		print(-1)


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = []
	ans = -1
	for i in range(n):
		(x, y) = map(int, input().split())
		arr.append((x, y))
	for i in arr:
		val = 0
		for j in arr:
			if abs(i[0] - j[0]) + abs(i[1] - j[1]) <= k:
				val += 1
		if val == n:
			ans = 1
			break
	print(ans)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def gift():
	for _ in range(t):
		(n, k) = list(map(int, input().split()))
		balls = []
		for i in range(n):
			ball = list(map(int, input().split()))
			balls.append(ball)
		ans = False
		for i in range(n):
			temAns = True
			for j in range(n):
				if j != n:
					if abs(balls[i][0] - balls[j][0]) + abs(balls[i][1] - balls[j][1]) > k:
						temAns = False
						break
			if temAns:
				ans = True
				break
		yield (1 if ans else -1)
t = int(input())
ans = gift()
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = [list(map(int, input().split())) for _ in range(n)]
	for i in range(n):
		if all((i == j or abs(w[i][0] - w[j][0]) + abs(w[i][1] - w[j][1]) <= k for j in range(n))):
			print(1)
			break
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	any = False
	a = []
	b = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	for j in range(n):
		(x, y) = (a[j], b[j])
		ok = True
		for i in range(n):
			if i == j:
				pass
			elif abs(a[i] - x) + abs(b[i] - y) > k:
				ok = False
				break
		if ok:
			any = True
			break
	if any:
		print(1)
	else:
		print(-1)


T = int(input())
for __ in range(T):
	(n, k) = map(int, input().split())
	flag = 0
	listi = []
	for i in range(n):
		(a, b) = map(int, input().split())
		listi.append([a, b])
	for x in range(n):
		for y in range(n):
			diff = abs(listi[x][0] - listi[y][0]) + abs(listi[x][1] - listi[y][1])
			if diff > k:
				break
		else:
			flag = 1
			break
	if flag == 1:
		print('1')
	else:
		print('-1')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	r = []
	for i in range(n):
		(x, y) = map(int, input().split())
		r.append([x, y])
	flag = False
	for i in range(n):
		x0 = r[i][0]
		y0 = r[i][1]
		for j in range(n):
			x = r[j][0]
			y = r[j][1]
			if abs(x0 - x) + abs(y0 - y) > k:
				break
		else:
			flag = True
	if flag:
		print(1)
	else:
		print(-1)


test_cases = int(input())
res = []
for test in range(test_cases):
	s = input()
	ls = s.split()
	n = int(ls[0])
	k = int(ls[1])
	points = []
	for i in range(n):
		s = input()
		ls = s.split()
		points.append([int(ls[0]), int(ls[1])])
	val = -1
	for i in range(n):
		flag = 1
		for j in range(n):
			if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) > k:
				flag = -1
				break
		if flag == 1:
			val = 1
			break
	res.append(val)
for value in res:
	print(value)


def Man(x, y):
	return abs(x[0] - y[0]) + abs(x[1] - y[1])
t = int(input())
for z in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = []
	for i in range(n):
		(x, y) = [int(i) for i in input().split()]
		arr.append([x, y])
	flag = -1
	for i in range(n):
		flag2 = 0
		for j in range(n):
			if Man(arr[i], arr[j]) > k:
				flag2 = 1
				break
		if flag2 == 0:
			flag = 1
			break
	print(flag)


import sys
input = sys.stdin.readline
n = int(input())

def manhattan(point1, point2):
	return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])
for _ in range(n):
	(numPoint, attraction) = map(int, input().split())
	point = []
	flag = False
	for _ in range(numPoint):
		(x, y) = map(int, input().split())
		point.append([x, y])
	for i in range(numPoint):
		flag = True
		for j in range(numPoint):
			if i == j:
				continue
			if attraction >= manhattan(point[i], point[j]):
				continue
			else:
				flag = False
				break
		if flag == True:
			break
	if flag == True:
		print(1)
	else:
		print(-1)


from sys import stdin
from math import inf
input = lambda : stdin.readline().strip()
ipnut = input

def dist(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1]) <= k
for i in range(int(input())):
	(n, k) = map(int, ipnut().split())
	coord = []
	for i in range(n):
		coord.append(tuple(map(int, input().split())))
	f = -1
	for i in range(n):
		fl = 1
		for j in range(n):
			if not dist(coord[i], coord[j]):
				fl = 0
		if fl:
			f = 1
			break
	print(f)


from sys import stdin, stdout

def doit():
	global points, n, k
	for i in range(n):
		(x1, y1) = points[i]
		ok = True
		for j in range(n):
			(x2, y2) = points[j]
			distance = abs(x1 - x2) + abs(y1 - y2)
			if distance > k:
				ok = False
				break
		if ok:
			return 1
	return -1
test = int(stdin.readline())
for _ in range(test):
	(n, k) = map(int, stdin.readline().split())
	points = []
	for i in range(n):
		(x, y) = map(int, stdin.readline().split())
		points.append([x, y])
	print(doit())


import sys

def main(balls, k):
	n = len(balls)
	(x, y) = balls[0]
	for (x, y) in balls:
		good = True
		for (_x, _y) in balls:
			if abs(x - _x) + abs(y - _y) > k:
				good = False
				continue
		if good:
			return 1
	return -1
(n, k) = (-1, -1)
n_tests = -1
balls = []
for line in sys.stdin:
	if n_tests == -1:
		n_tests = int(line.strip())
		(n, k) = (-1, -1)
	elif n == k == -1:
		(n, k) = [int(c) for c in line.strip().split()]
	else:
		balls.append([int(c) for c in line.strip().split()])
		if len(balls) == n:
			print(main(balls, k))
			balls = []
			(n, k) = (-1, -1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	y = 0
	(c, d) = ([], [])
	for i in range(n):
		(a, b) = map(int, input().split())
		c.append(a)
		d.append(b)
	for i in range(n):
		x = 0
		for j in range(n):
			if abs(c[i] - c[j]) + abs(d[i] - d[j]) <= k:
				x = x + 1
		if x > y:
			y = x
	if y == n:
		print(1)
	else:
		print(-1)


test_case = int(input())
for ix in range(test_case):
	n = [int(x) for x in input().split()]
	no = n[0]
	pow = n[1]
	dist = []
	flag = False
	for ixx in range(no):
		point = [int(x) for x in input().split()]
		dist.append(point)
	for i in range(no):
		count = 0
		for j in range(no):
			d = abs(dist[i][0] - dist[j][0]) + abs(dist[i][1] - dist[j][1])
			if d <= pow:
				count = count + 1
		if count == no:
			flag = True
			break
	if flag:
		print('1')
	else:
		print('-1')


from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	points = []
	for i in range(n):
		(x, y) = map(int, input().split())
		points.append((x, y))
	flag = False
	for i in range(n):
		flagg = False
		for j in range(n):
			if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) > k:
				flagg = True
				break
		if flagg == False:
			flag = True
			break
	if flag == False:
		print(-1)
	else:
		print(1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = [list(map(int, input().split())) for __ in range(n)]
	f = 1
	for i in range(n):
		(x0, y0) = c[i]
		for j in range(n):
			(x1, y1) = c[j]
			if abs(x1 - x0) + abs(y1 - y0) > k:
				f = -1
				break
		else:
			f = 1
			break
	print(f)


t = int(input())
for T in range(t):
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		l = list(map(int, input().split()))
		a.append(l)
	for i in range(n):
		ans = 1
		for j in range(n):
			if abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]) > k:
				ans = -1
				break
		if ans == 1:
			break
	print(ans)


for _ in range(int(input())):
	x = []
	y = []
	count = 0
	(n, k) = map(int, input().split())
	for _ in range(n):
		(a, b) = map(int, input().split())
		x.append(a)
		y.append(b)
	for i in range(n):
		flag = True
		for j in range(n):
			if abs(x[i] - x[j]) + abs(y[i] - y[j]) <= k:
				continue
			else:
				flag = False
				break
		if flag == True:
			count = 1
			break
	if count == 1:
		print('1')
	else:
		print('-1')


for z in range(int(input())):
	(n, k) = map(int, input().split())
	matrix = []
	for i in range(n):
		a = []
		(fir, sec) = map(int, input().split())
		a.append(fir)
		a.append(sec)
		matrix.append(a)
	res = -1
	for i in range(n):
		mil = 1
		for j in range(n):
			if i != j and k < abs(matrix[i][0] - matrix[j][0]) + abs(matrix[i][1] - matrix[j][1]):
				mil = 0
				break
		if mil:
			res = 1
			break
	print(res)


def dis(x1, y1, x2, y2):
	ans = abs(x1 - x2) + abs(y1 - y2)
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = []
	for _ in range(n):
		(x, y) = map(int, input().split(' '))
		arr.append([x, y])
	d = []
	v = []
	ans = -1
	for i in range(n):
		d = []
		for j in range(n):
			p = dis(arr[i][0], arr[i][1], arr[j][0], arr[j][1])
			d.append(p)
		c = 0
		for item in d:
			if item <= k:
				c = c + 1
		if c == n:
			ans = 1
			break
	print(ans)


n = int(input())
while n:
	m = list(map(int, input().split()))
	list1 = []
	i = 0
	while i != m[0]:
		list2 = list(map(int, input().split()))
		list1.append(list2)
		i = i + 1
	for i in range(m[0]):
		flag = 0
		for j in range(m[0]):
			if abs(list1[i][0] - list1[j][0]) + abs(list1[i][1] - list1[j][1]) <= m[1]:
				flag = flag + 1
		if flag == m[0]:
			break
	if flag == m[0]:
		print(1)
	else:
		print(-1)
	n = n - 1


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	p = []
	c = 0
	for i in range(n):
		x = [int(i) for i in input().split()]
		p.append(x)
	for i in range(0, n):
		(xi, yi) = p[i]
		for j in range(0, n):
			(xj, yj) = p[j]
			d = abs(xi - xj) + abs(yi - yj)
			if d > k:
				break
			if j == n - 1:
				c = 1
				print(1)
		if c == 1:
			break
	if c == 0:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	xy = [tuple(map(int, input().split())) for i in range(n)]
	ans = -1
	for (x, y) in xy:
		flag = True
		for (x2, y2) in xy:
			dx = abs(x2 - x)
			dy = abs(y2 - y)
			if dx + dy <= k:
				continue
			else:
				flag = False
				break
		if flag:
			ans = 1
			break
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = [*map(int, input().split())]
	l = list()
	for el in range(n):
		l.append([*map(int, input().split())])
	ans = -1
	for i in range(n):
		cnt = 0
		for j in range(n):
			if i == j:
				continue
			if abs(l[i][0] - l[j][0]) + abs(l[i][1] - l[j][1]) > k:
				break
			cnt += 1
		if cnt == n - 1:
			ans = 1
			break
	print(ans)


rn = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rns = lambda : map(int, input().split())
rs = lambda : input()
yn = lambda x: print('Yes') if x else print('No')
YN = lambda x: print('YES') if x else print('NO')
for _ in range(rn()):
	(n, k) = rns()
	points = []
	ans = -1
	for i in range(n):
		points.append(rl())
	for i in range(n):
		b = []
		for j in range(n):
			if i != j:
				b.append(abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]))
		if all([i <= k for i in b]):
			ans = 1
			break
	print(ans)


n_tests = int(input())
for test in range(n_tests):
	[n, k] = input().split(' ')
	k = int(k)
	d = []
	n = int(n)
	for i in range(n):
		p = input().split(' ')
		p = [int(w) for w in p]
		d.append(p)
	md = []
	t = False
	for i in range(n):
		q = d[i]
		a = 0
		for j in range(n):
			s = abs(q[0] - d[j][0]) + abs(q[1] - d[j][1])
			if s <= k:
				a += 1
		if a == n:
			t = True
			break
	if t:
		print(1)
	else:
		print(-1)


def manhattan(a, b):
	dx = abs(a[0] - b[0])
	dy = abs(a[1] - b[1])
	distance = dy + dx
	return distance

def operation(points, k):
	for p in points:
		flag = True
		for i in range(len(points)):
			if manhattan(p, points[i]) > k:
				flag = False
				break
		if flag:
			return 1
	return -1
cases = int(input())
points = []
for c in range(cases):
	(npoints, k) = tuple((int(a) for a in input().split(' ')))
	for i in range(npoints):
		point = [int(a) for a in input().split(' ')]
		points.append(point)
	print(operation(points, k))
	points = []


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	points = []
	for _ in range(n):
		points.append(list(map(int, sys.stdin.readline().split())))
	found = False
	for point1 in points:
		good = True
		for point2 in points:
			dist = abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])
			if dist > k:
				good = False
				break
		if good:
			found = True
			break
	print(1 if found else -1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append([x, y])
	g = 0
	for i in range(n):
		f = 0
		for j in range(n):
			dis = abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1])
			if dis <= k:
				continue
			else:
				f = 1
				break
		if f == 0:
			print(1)
			g = 1
			break
	if g == 0:
		print(-1)


try:

	def dist(x, y, a, b):
		s = abs(x - a) + abs(y - b)
		return s
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		x = []
		y = []
		for _ in range(n):
			(a, b) = map(int, input().split())
			x.append(a)
			y.append(b)
		i = 0
		l = 0
		for i in range(n):
			j = 0
			for j in range(n):
				d = dist(x[i], y[i], x[j], y[j])
				if d > k:
					break
				if j == n - 1:
					l = 1
			if l == 1:
				print(1)
				break
		if l == 0:
			print(-1)
except:
	pass


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	x = []
	y = []
	for j in range(n):
		p = list(map(int, input().split()))
		x.append(p[0])
		y.append(p[1])
	ll = len(x)
	c = 0
	f = 0
	for i in range(ll):
		c = 0
		for j in range(ll):
			if j == i:
				continue
			else:
				s = abs(x[i] - x[j]) + abs(y[i] - y[j])
				if s <= k:
					c += 1
				else:
					break
		if c == n - 1 and f == 0:
			f = 1
			print(1)
	if f == 0:
		print(-1)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List
sys.setrecursionlimit(99999)
(t,) = map(int, input().split())
for _ in range(t):
	(n, k) = map(int, input().split())
	ps = []
	for i in range(n):
		(x, y) = map(int, input().split())
		ps.append([x, y])
	d = [0] * n
	for a in range(n):
		for i in range(a + 1, n):
			if abs(ps[i][0] - ps[a][0]) + abs(ps[i][1] - ps[a][1]) <= k:
				d[a] += 1
				d[i] += 1
	if n - 1 in d:
		print(1)
	else:
		print(-1)


from math import *
from bisect import *
from collections import *
from random import *
from decimal import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, k) = ma()
	r = []
	for i in range(n):
		(x, y) = ma()
		r.append([x, y])
	fl = 0
	for i in range(n):
		co = 0
		for j in range(n):
			m = abs(r[j][0] - r[i][0]) + abs(r[j][1] - r[i][1])
			if m <= k:
				co += 1
		if co == n:
			fl = 1
			break
	if fl:
		print(1)
	else:
		print(-1)


t = int(input())
for i in range(t):
	[n, k] = map(int, input().split())
	points = []
	for i in range(n):
		[x, y] = map(int, input().split())
		points.append([x, y])
	for p in points:
		flag = True
		for q in points:
			if abs(p[0] - q[0]) + abs(p[-1] - q[-1]) > k:
				flag = False
				break
		if flag == True:
			break
	if flag:
		print(1)
	else:
		print(-1)