Chef has $N$ points (numbered $1$ through $N$) in a 2D Cartesian coordinate system. For each valid $i$, the $i$-th point is $(x_i, y_i)$. He also has a fixed integer $c$ and he may perform operations of the following type: choose a point $(x_i, y_i)$ and move it to $(x_i + c, y_i + c)$ or $(x_i - c, y_i - c)$.
Now, Chef wants to set up one or more checkpoints (points in the same coordinate system) and perform zero or more operations in such a way that after they are performed, each of his (moved) $N$ points is located at one of the checkpoints.
Chef's primary objective is to minimise the number of checkpoints. Among all options with this minimum number of checkpoints, he wants to choose one which minimises the number of operations he needs to perform.
Can you help Chef find the minimum number of required checkpoints and the minimum number of operations he needs to perform to move all $N$ points to these checkpoints?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $c$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $x_i$ and $y_i$.

-----Output-----
For each test case, print a single line containing two integers ― the minimum number of checkpoints and the minimum number of moves.

-----Constraints-----
- $1 \le T \le 5$
- $1 \le N \le 5 \cdot 10^5$
- $|x_i|, |y_i| \le 10^9$ for each valid $i$
- $0 < c \le 10^9$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$

-----Example Input-----
1
3 1
1 1
1 0
3 2

-----Example Output-----
2 2

-----Explanation-----
Example case 1: One optimal solution is to set up checkpoints at coordinates $(1, 1)$ and $(1, 0)$. Since the points $(1, 1)$ and $(1, 0)$ are already located at checkpoints, Chef can just move the point $(3, 2)$ to the checkpoint $(1, 0)$ in two moves: $(3, 2) \rightarrow (2, 1) \rightarrow (1, 0)$.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
from collections import defaultdict
R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(n, c) = R()
	d = defaultdict(list)
	for _ in range(n):
		(x, y) = R()
		d[y - x, x % c].append(x)
	d = tuple(d.values())
	for l in d:
		l.sort()
	r = sum((l[-i - 1] - l[i] for l in d for i in range(len(l) // 2)))
	print(len(d), r // c)


for _ in range(int(input())):
	(n, c) = list(map(int, input().split()))
	numpoints = 0
	moves = 0
	d = dict()
	for f in range(n):
		(a, b) = list(map(int, input().split()))
		dif = a - b
		mod = a % c
		if dif not in d:
			d[dif] = {}
		if mod not in d[dif]:
			d[dif][mod] = []
		d[dif][mod].append(a)
	for i in d:
		for j in d[i]:
			numpoints += 1
			num = len(d[i][j])
			d[i][j].sort()
			mid = d[i][j][int(num / 2)]
			for k in d[i][j]:
				moves += abs(int((k - mid) / c))
	print(numpoints, moves)


from collections import defaultdict as dd
from collections import Counter as cc
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, c) = I()
	d = dd(list)
	for i in range(n):
		(x, y) = I()
		d[x - y].append(x)
	(cp, p) = (len(d), 0)
	for i in d.keys():
		x = d[i]
		l = dd(list)
		for j in range(len(x)):
			l[x[j] % c].append(x[j] // c)
		for j in l.keys():
			pp = sorted(l[j])
			k = pp[len(pp) // 2]
			for o in pp:
				p += abs(k - o)
		cp += len(l) - 1
	print(cp, p)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, c) = [int(x) for x in input().strip().split()]
	arr = defaultdict(list)
	for i in range(n):
		(x, y) = [int(z) for z in input().strip().split()]
		arr[x - y].append([x, y])
	cp = 0
	m = 0
	for i in arr:
		if len(arr[i]) == 1:
			cp += 1
		else:
			d = defaultdict(list)
			temparr = sorted(arr[i])
			d[0].append(temparr[0])
			for j in range(1, len(temparr)):
				d[(temparr[0][0] - temparr[j][0]) % c].append(temparr[j])
			for j in d:
				cp += 1
				if len(d[j]) == 1:
					pass
				else:
					temparr = d[j]
					p = 0
					q = len(temparr) - 1
					while p < q:
						m += abs((temparr[p][0] - temparr[q][0]) // c)
						p += 1
						q -= 1
	print(cp, m)


from collections import defaultdict
T = int(input().rstrip())
for tt in range(T):
	(N, c) = list(map(int, input().rstrip().split(' ')))
	hh = defaultdict(list)
	for i in range(N):
		(x, y) = list(map(int, input().rstrip().split(' ')))
		hh[x - y, (x % c + c) % c].append(x)
	opr = 0
	for j in hh:
		arr = hh[j]
		arr.sort()
		med = arr[len(arr) // 2]
		tp = 0
		for k in arr:
			tp += abs(med - k) // c
		opr += tp
	print(len(hh), int(opr))


def cnt(x):
	return sum((x[-i - 1] - x[i] for i in range(len(x) // 2)))
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	d = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		k = (x - y, x % c)
		if k in d:
			d[k].append(x // c)
		else:
			d[k] = [x // c]
	print(len(d), sum((cnt(sorted(v)) for v in d.values())))


for _ in range(int(input())):
	d = dict()
	(n, c) = list(map(int, input().split()))
	numCheckPoints = 0
	moves = 0
	for _ in range(n):
		(x, y) = list(map(int, input().split()))
		dif = x - y
		mod = x % c
		if dif not in d:
			d[dif] = {}
		if mod not in d[dif]:
			d[dif][mod] = []
		d[dif][mod].append(x)
	for i in d:
		for j in d[i]:
			numCheckPoints += 1
			num = len(d[i][j])
			d[i][j].sort()
			if num % 2:
				mid = d[i][j][int(num / 2)]
				for k in d[i][j]:
					moves += abs(int((k - mid) / c))
			else:
				choice1 = 0
				mid = d[i][j][int(num / 2)]
				for k in d[i][j]:
					choice1 += abs(int((k - mid) / c))
				choice2 = 0
				mid = d[i][j][int(num / 2) - 1]
				for k in d[i][j]:
					choice2 += abs(int((k - mid) / c))
				moves += min(choice1, choice2)
	print(numCheckPoints, moves)


for i in range(int(input())):
	(n, c) = map(int, input().split())
	pts = {}
	moves = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		if (y - x, x % c) in pts:
			pts[y - x, x % c].append(x)
		else:
			pts[y - x, x % c] = [x]
	for i in pts:
		arc = sorted(pts[i])
		for j in arc:
			moves = moves + abs(j - arc[len(arc) // 2]) // c
	print(len(pts), moves)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

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

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, c) = get_ints()
	store = defaultdict(list)
	for i in range(n):
		(x, y) = get_ints()
		store[x - y, (x % c + c) % c].append([x, y])
	ans = len(store)
	moves = 0
	for key in store:
		b = store[key]
		b.sort()
		(x_, y_) = b[len(b) // 2]
		for (x, y) in b:
			moves += abs(x - x_) // c
	print(ans, moves)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(N, c) = map(int, input().split())
	A = []
	B = {}
	for i in range(N):
		(x, y) = map(int, input().split())
		A.append([x, y])
		try:
			B[x - y].append(x)
		except:
			B[x - y] = [x]
	C = {}
	tc = 0
	to = 0
	for val in B:
		arr = B[val]
		D = {}
		arr.sort()
		for i in arr:
			try:
				D[i % c].append(i)
			except:
				D[i % c] = [i]
		tc = tc + len(D)
		for val1 in D:
			arr = D[val1]
			my = arr[(len(arr) - 1) // 2]
			for i in arr:
				to = to + abs(my - i) // c
	print(tc, to)


for _ in range(int(input())):
	(n, c) = [int(i) for i in input().split()]
	a = [[int(i) for i in input().split()] for j in range(n)]
	dp = {}
	for i in range(n):
		val = a[i][0] - a[i][1]
		dp[val] = []
	for i in range(n):
		val = a[i][0] - a[i][1]
		dp[val].append(i)
	o = []
	for i in dp.keys():
		o1 = []
		for j in dp[i]:
			o1.append(a[j][0])
		o.append(o1)
	ct = 0
	c1 = 0
	for i in o:
		x = i
		x.sort()
		dp = {}
		for j in range(len(x)):
			dp[x[j] % c] = []
		for j in range(len(x)):
			dp[x[j] % c].append(x[j])
		ct += len(dp)
		for j in dp.values():
			f = [0] * len(j)
			b = [0] * len(j)
			for k in range(1, len(j)):
				f[k] = k * ((j[k] - j[k - 1]) // c) + f[k - 1]
			for k in range(len(j) - 2, -1, -1):
				b[k] = (len(j) - 1 - k) * ((j[k + 1] - j[k]) // c) + b[k + 1]
			minn = 10 ** 18
			for k in range(len(j)):
				minn = min(minn, b[k] + f[k])
			c1 += minn
	print(ct, c1)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	temp = {}
	group = {}
	for i in range(n):
		if arr[i][0] - arr[i][1] not in temp:
			temp[arr[i][0] - arr[i][1]] = [arr[i][0]]
		else:
			temp[arr[i][0] - arr[i][1]].append(arr[i][0])
	noc = 0
	nop = 0
	for d in temp:
		for x in temp[d]:
			if x % c not in group:
				group[x % c] = [x]
			else:
				group[x % c].append(x)
		for e in group:
			noc += 1
			grp = sorted(group[e])
			med = grp[int(len(grp) / 2)]
			for i in range(len(grp)):
				nop += abs(grp[i] - med) // c
		group.clear()
	print(noc, nop)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	(pts_line, summation) = ({}, 0)
	for _ in range(n):
		(x, y) = map(int, input().split())
		if (y - x, x % c) in pts_line:
			pts_line[y - x, x % c].append(x)
		else:
			pts_line[y - x, x % c] = [x]
	for pt in pts_line:
		arc = sorted(pts_line[pt])
		for metre in arc:
			summation += abs(metre - arc[len(arc) // 2]) // c
	print(len(pts_line), summation)


for _ in range(int(input())):
	(N, c) = [int(i) for i in input().split()]
	(coordinates, temp, checkpoints, operations) = ([], [], 0, 0)
	for i in range(N):
		(x, y) = [int(i) for i in input().split()]
		temp.append(x)
		temp.append(y)
		coordinates.append(temp)
		temp = []
	dict1 = {}
	for i in coordinates:
		try:
			dict1[i[0] - i[1]].append(i[0])
		except:
			dict1[i[0] - i[1]] = [i[0]]
	for i in dict1:
		list1 = dict1[i]
		list1.sort()
		dict2 = {}
		for j in list1:
			try:
				dict2[j % c].append(j)
			except:
				dict2[j % c] = [j]
		checkpoints += len(dict2)
		for k in dict2:
			list2 = dict2[k]
			median = list2[(len(list2) - 1) // 2]
			for ele in list2:
				operations += int(abs(median - ele) // c)
	print(checkpoints, operations)


from collections import defaultdict
R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(n, c) = R()
	c *= 2
	d = defaultdict(list)
	for _ in range(n):
		(x, y) = R()
		s = x + y
		d[y - x, s % c].append(s)
	r = 0
	for (x, l) in d.items():
		l.sort()
		r += sum((y - x for (x, y) in zip(l[:len(l) // 2], l[::-1])))
	print(len(d), r // c)


import sys
import math
import collections
from sys import stdin, stdout, setrecursionlimit
import bisect as bs
setrecursionlimit(2 ** 20)
M = 10 ** 9 + 7
T = int(stdin.readline())
for _ in range(T):
	(n, C) = list(map(int, stdin.readline().split()))
	x = []
	y = []
	for i in range(n):
		(tmpx, tmpy) = list(map(int, stdin.readline().split()))
		x.append(tmpx)
		y.append(tmpy)
	di = []
	d = {}
	m = {}
	for i in range(n):
		t = x[i] - y[i]
		r = x[i] % C
		if (t, r) not in d:
			d[t, r] = []
		d[t, r].append(x[i])
	c = len(d)
	ans = 0
	cnt = 0
	for k in d:
		tmp = d[k].copy()
		tmp.sort()
		if len(d[k]) % 2 == 0:
			(tmp1, tmp2) = (0, 0)
			t1 = len(d[k]) // 2
			t2 = len(d[k]) // 2 - 1
			t3 = (tmp[t1] + tmp[t2]) // 2
			p1 = t3 - t3 % C + k[1]
			p2 = p1 + C
			for j in d[k]:
				tmp1 += abs(p1 - j) // C
			for j in d[k]:
				tmp2 += abs(p2 - j) // C
			cnt += min(tmp1, tmp2)
		if len(d[k]) % 2 == 1:
			ln = len(tmp) // 2
			for j in d[k]:
				cnt += abs(j - tmp[ln]) // C
	print(str(c) + ' ' + str(cnt))


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	points = []
	dic = {}
	for i in range(n):
		(a, b) = map(int, input().split())
		points.append((a, b))
	for i in range(n):
		a = points[i]
		if a[0] - a[1] in dic:
			dic[a[0] - a[1]].append(points[i])
		else:
			dic[a[0] - a[1]] = [points[i]]
	checkpoints = 0
	operations = 0
	for i in dic:
		d = {}
		for j in dic[i]:
			if j[0] % c in d:
				d[j[0] % c].append(j[0])
			else:
				d[j[0] % c] = [j[0]]
		for j in d:
			d[j].sort()
			checkpoints += 1
			m = len(d[j]) // 2
			for k in d[j]:
				operations += abs(d[j][m] - k) // c
	print(checkpoints, operations)


import collections
t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	hashmap = collections.defaultdict(list)
	for i in range(n):
		(x, y) = map(int, input().split())
		hashmap[x - y, x % c].append(x)
	steps = 0
	total = 0
	for each in hashmap:
		hashmap[each].sort()
		med = hashmap[each][len(hashmap[each]) // 2]
		for val in hashmap[each]:
			total += abs(med - val)
	print(len(hashmap), total // c)


T = int(input())
for i in range(T):
	a = input().split()
	N = int(a[0])
	c = int(a[1])
	D = {}
	for j in range(N):
		b = input().split()
		x = int(b[0])
		y = int(b[1])
		t = (x - y, x % c)
		try:
			D[t] += [x // c]
		except:
			D[t] = [x // c]
	q = len(D)
	p = 0
	for k in D.values():
		L = k
		L.sort()
		w = len(L)
		A = L[:w // 2]
		B = L[(w + 1) // 2:]
		p += sum(B) - sum(A)
	print(q, p)


import math
import collections
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left as bsl
from bisect import bisect_right as bsr
import heapq as hq
setrecursionlimit(2 ** 20)
t = 1
t = int(stdin.readline())
for _ in range(t):
	(n, c) = list(map(int, stdin.readline().rstrip().split()))
	(X, Y) = ([], [])
	for i in range(n):
		(t1, t2) = list(map(int, stdin.readline().rstrip().split()))
		X.append(t1)
		Y.append(t2)
	d = {}
	mi = {}
	mx = {}
	for i in range(n):
		(x, y) = (X[i], Y[i])
		if (x - y, x % c) not in d:
			d[x - y, x % c] = []
			mi[x - y, x % c] = 0
		d[x - y, x % c].append((x, y))
		mi[x - y, x % c] += x
	noc = len(d)
	cnt = 0
	for i in d:
		a = d[i][:]
		a.sort()
		if len(d[i]) % 2 == 0:
			t = mi[i] // len(d[i])
			(tmp1, tmp2) = (0, 0)
			t1 = len(d[i]) // 2
			t2 = len(d[i]) // 2 - 1
			t3 = (a[t1][0] + a[t2][0]) // 2
			p1 = t3 - t3 % c + i[1]
			p2 = p1 + c
			for j in d[i]:
				tmp1 += abs(p1 - j[0]) // c
			for j in d[i]:
				tmp2 += abs(p2 - j[0]) // c
			cnt += min(tmp1, tmp2)
		if len(d[i]) % 2 == 1:
			ln = len(a) // 2
			for j in d[i]:
				cnt += abs(j[0] - a[ln][0]) // c
	print(str(noc) + ' ' + str(cnt))


t = int(input())
while t:
	(n, c) = map(int, input().split())
	u = c
	a = []
	d = {}
	for i in range(n):
		(p, q) = map(int, input().split())
		a += [[p, q]]
		x = min(p, q)
		d[p - q] = []
	for i in range(n):
		(y, z) = (a[i][0], a[i][1])
		m = y - z
		d[m].append(a[i][0])
	e = []
	for i in d.values():
		e.append(i)
	g = []
	for k in e:
		d = {}
		for i in range(len(k)):
			d[k[i] % c] = []
		for i in range(len(k)):
			d[k[i] % c].append(k[i])
		for i in d.values():
			g.append(i)
	c = 0
	print(len(g), end=' ')
	for i in range(len(g)):
		g[i].sort()
		med = len(g[i]) // 2
		for j in range(len(g[i])):
			c += abs(g[i][j] - g[i][med]) // u
	print(c)
	t -= 1


import sys
import math
import collections
from sys import stdin, stdout, setrecursionlimit
import bisect as bs
setrecursionlimit(2 ** 20)
M = 10 ** 9 + 7

def solve():
	(n, c) = list(map(int, stdin.readline().split()))
	xc = [0] * n
	yc = [0] * n
	ans1 = 0
	ans2 = 0
	d = {}
	for i in range(n):
		(xc[i], yc[i]) = list(map(int, stdin.readline().split()))
		if (xc[i] - yc[i], xc[i] % c) not in d:
			d[xc[i] - yc[i], xc[i] % c] = []
		d[xc[i] - yc[i], xc[i] % c].append(xc[i])
	for i in d:
		ans1 += 1
		rem = i[1]
		a = d[i][:]
		a.sort()
		s1 = len(d[i])
		s2 = 0
		if s1 % 2 == 1:
			ind = a[s1 // 2]
			for j in a:
				s2 = s2 + abs((j - ind) // c)
			ans2 += s2
		else:
			sum1 = a[s1 // 2] + a[s1 // 2 - 1]
			ind1 = sum1 // 2
			ind1 = ind1 - ind1 % c + rem
			ind2 = ind1
			s2 = 0
			s3 = 0
			for j in a:
				s2 = s2 + abs((j - ind1) // c)
			for j in a:
				s3 = s3 + abs((j - ind2) // c)
			ans2 = ans2 + min(s2, s3)
	print(ans1, ans2)
t = 1
t = int(stdin.readline())
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	(n, c) = list(map(lambda x: int(x), input().split()))
	hashmap = {}
	for i in range(0, n):
		(x, y) = list(map(lambda x: int(x), input().split()))
		mod_x = x % c
		mod_y = y % c
		if (mod_x, mod_y, x - y) not in hashmap:
			hashmap[mod_x, mod_y, x - y] = []
		hashmap[mod_x, mod_y, x - y].append((x, y))
	print(len(hashmap), end=' ')
	total_operations = 0
	for key in hashmap:
		hashmap[key] = sorted(hashmap[key], key=lambda x: x[0])
		initial = hashmap[key][len(hashmap[key]) // 2][0]
		for (x, y) in hashmap[key]:
			total_operations += abs((x - initial) // c)
	print(total_operations)


for t in range(int(input())):
	(n, c) = map(int, input().split())
	d = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		t = x - y
		if t not in d:
			d[t] = [[x, y]]
		else:
			d[t].append([x, y])
	checkpoints = 0
	moves = 0
	for i in d:
		points = d[i]
		mod = {}
		for j in range(len(points)):
			t = points[j][0] % c
			if t not in mod:
				mod[t] = [points[j]]
			else:
				mod[t].append(points[j])
		for j in mod:
			checkpoints += 1
			check = mod[j]
			check = sorted(check, key=lambda x: x[0])
			mid = check[len(check) // 2][0]
			for k in range(len(check)):
				moves += abs(mid - check[k][0]) // c
	print(checkpoints, moves)


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
for _ in range(inp()):
	(n, c) = ip()
	d = {}
	for i in range(n):
		(a, b) = ip()
		t = d.get(a - b, {})
		tt = t.get((a % c, b % c), [])
		tt.append([a, b])
		t[a % c, b % c] = tt
		d[a - b] = t
	ans = 0
	ct = 0
	for i in d:
		for j in d[i]:
			ct += 1
			t = sorted(d[i][j])
			mid = t[len(t) // 2][0]
			for (k, kk) in t:
				ans += abs(k - mid) // c
	print(ct, ans)


import math
import sys
sys.setrecursionlimit(10 ** 4)

def Divisors(n):
	l = []
	i = 2
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
		i = i + 1
	return l

def SieveOfEratosthenes(n):
	l = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			l.append(p)
	return l

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return l

def Factors(n):
	result = []
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			if i == n / i:
				result.append(i)
			else:
				result.append(i)
				result.append(n // i)
	result.append(1)
	result.append(n)
	return result

def maxSubArraySum(a):
	max_so_far = 0
	max_ending_here = 0
	size = len(a)
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far

def longestsubarray(arr, n, k):
	current_count = 0
	max_count = 0
	for i in range(0, n, 1):
		if arr[i] % k != 0:
			current_count += 1
		else:
			current_count = 0
		max_count = max(current_count, max_count)
	return max_count

def main():
	(n, c) = list(map(int, input().split()))
	l = []
	for j in range(0, n):
		l1 = list(map(int, input().split()))
		l.append(l1)
	d = {}
	for j in range(0, n):
		l1 = []
		l1.append(l[j][0] - l[j][1])
		l1.append((l[j][0] % c + c) % c)
		l1 = tuple(l1)
		d[l1] = []
	for j in range(0, n):
		l1 = []
		l1.append(l[j][0] - l[j][1])
		l1.append((l[j][0] % c + c) % c)
		l1 = tuple(l1)
		d[l1].append(l[j][0])
	c1 = len(d)
	m1 = 0
	for j in d:
		l2 = d[j]
		l2.sort()
		for p in range(0, len(l2)):
			m1 += abs(l2[p] - l2[len(l2) // 2]) // c
	print(c1, m1)
t = int(input())
for i in range(0, t):
	main()


t = int(input())
for _ in range(t):
	(N, c) = map(int, input().split())
	lines = {}
	summa = 0
	for _ in range(N):
		(x, y) = map(int, input().split())
		if (y - x, x % c) in lines:
			lines[y - x, x % c].append(x)
		else:
			lines[y - x, x % c] = [x]
	for b in lines:
		line = sorted(lines[b])
		m = len(line) // 2
		for l in line:
			summa += abs(l - line[m]) // c
	print(len(lines), summa)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	dict = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		diff = x - y
		if diff in dict:
			dict[diff].append(x)
		else:
			dict[diff] = [x]
	a = 0
	b = 0
	for i in dict:
		arr = dict[i]
		xdict = {}
		for j in arr:
			x = j % c
			if x in xdict:
				xdict[x].append(j)
			else:
				xdict[x] = [j]
		for j in xdict:
			a += 1
			final = sorted(xdict[j])
			mid = final[len(final) // 2]
			for k in final:
				b += abs(k - mid) // c
	print(a, b)


for t in range(int(input())):
	(n, c) = map(int, input().split())
	E = []
	dic = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		E.append([x, y])
		dic[x - y] = []
	for i in E:
		dic[i[0] - i[1]].append([i[0], i[1]])
	count = 0
	moves = 0
	for i in dic:
		sub = {}
		for j in dic[i]:
			(x, y) = (j[0], j[1])
			if sub.get(x % c, -1) == -1:
				sub[x % c] = [[x, y]]
			else:
				sub[x % c].append([x, y])
		count += len(sub)
		for j in sub:
			arr = sorted(sub[j])
			m1 = arr[len(arr) // 2][0]
			for k in arr:
				moves += abs(k[0] - m1) // c
	print(count, moves)


T = int(input())
for lmlm in range(T):
	a = input().split()
	n = int(a[0])
	c = int(a[1])
	D = {}
	for j in range(n):
		b = input().split()
		x = int(b[0])
		y = int(b[1])
		t = (x - y, x % c)
		try:
			D[t] += [x // c]
		except:
			D[t] = [x // c]
	q = len(D)
	p = 0
	for k in D.values():
		L = k
		L.sort()
		w = len(L)
		a1 = L[:w // 2]
		b1 = L[(w + 1) // 2:]
		p += sum(b1) - sum(a1)
	print(q, p)


from collections import defaultdict as dd
for _ in range(int(input())):
	cont = dd(list)
	(n, c) = list(map(int, input().split()))
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		cont[x - y, (x % c + c) % c].append((x, y))
	checkpoints = len(cont)
	moves = 0
	for i in cont:
		v = cont[i]
		v.sort()
		pivot = v[len(v) // 2]
		for j in v:
			moves += abs(pivot[0] - j[0]) // c
	print(checkpoints, moves)


from math import *
from collections import *
t = int(input())
while t:
	t -= 1
	(n, c) = map(int, input().split())
	de = {}
	for i in range(n):
		(x, y) = map(int, input().split())
		if (x - y, x % c, y % c) in de:
			de[x - y, x % c, y % c].append(x // c)
		else:
			de[x - y, x % c, y % c] = [x // c]
	tot = 0
	for i in de:
		x = de[i][:]
		x.sort()
		if len(x) > 1:
			l = len(x)
			tot += abs(sum(x[:l // 2]) - sum(x[(l + 1) // 2:]))
	print(len(de), tot)


from collections import defaultdict

def main():
	for _ in range(int(input())):
		(n, c) = map(int, input().split())
		if c == 0:
			c += 1
		a = [list(map(int, input().split())) for i in range(n)]
		(s, l, d, sd) = (set(), [], defaultdict(list), dict())
		for i in a:
			(x, y) = (i[0] - c * (i[0] // c), i[1] - c * (i[0] // c))
			if x < 0:
				(x, y) = (x + c, y + c)
			d[x, y].append(i)
		op = 0
		for i in d:
			d[i].sort()
		for i in d:
			if len(d[i]) % 2 == 1:
				al = len(d[i]) // 2
				for j in range(len(d[i])):
					op += abs((d[i][j][0] - d[i][al][0]) // c)
			else:
				(op1, op2) = (0, 0)
				al = len(d[i]) // 2
				for j in range(len(d[i])):
					op1 += abs((d[i][j][0] - d[i][al - 1][0]) // c)
				for j in range(len(d[i])):
					op2 += abs((d[i][j][0] - d[i][al][0]) // c)
				op += min(op1, op2)
		print(len(d), op)
main()


from collections import defaultdict
for x in range(int(input())):
	(n, r) = list(map(int, input().split()))
	d = defaultdict(list)
	p = defaultdict(list)
	for i in range(n):
		(a, b) = list(map(int, input().split()))
		if b - a < 0:
			d[a - b].append(a)
		else:
			p[b - a].append(a)
	if r > 0:
		k = 0
		s = 0
		for e in d:
			c = defaultdict(list)
			for f in d[e]:
				c[f % r].append(f)
			for i in c:
				L = c[i]
				L.sort()
				w = len(c[i])
				h = w // 2
				for t in range(w):
					s += abs(L[t] - L[h]) // r
				k += 1
		for e in p:
			c = defaultdict(list)
			for f in p[e]:
				c[f % r].append(f)
			for i in c:
				L = c[i]
				L.sort()
				w = len(c[i])
				h = w // 2
				for t in range(w):
					s += abs(L[t] - L[h]) // r
				k += 1
		print(k, s)
	else:
		k = 0
		s = 0
		for e in d:
			k += len(d[e])
		for e in p:
			k += len(p[e])
		print(k, s)


def find2(arr, c):
	arr.sort()
	if len(arr) == 1:
		return 0
	dpleft = [0]
	for i in range(len(arr) - 1):
		x1 = arr[i][0]
		x2 = arr[i + 1][0]
		k = (x2 - x1) // c
		dpleft.append(dpleft[-1] + k * len(dpleft))
	dpright = [0]
	for i in range(len(arr) - 1, 0, -1):
		x1 = arr[i][0]
		x2 = arr[i - 1][0]
		k = (x1 - x2) // c
		dpright.append(dpright[-1] + k * len(dpright))
	dpleft.pop(0)
	dpright.pop(0)
	dpright.reverse()
	min_moves = min(dpright[0], dpleft[-1])
	for i in range(1, len(arr) - 1):
		left = dpleft[i - 1]
		right = dpright[i]
		min_moves = min(min_moves, left + right)
	return min_moves

def find(arr, c):
	mods = {}
	for (x, y) in arr:
		mod = (x % c, y % c)
		if mod not in mods.keys():
			mods[mod] = []
		mods[mod].append((x, y))
	points = len(mods)
	moves = 0
	for i in mods.keys():
		moves += find2(mods[i], c)
	return (points, moves)

def solve(diff, c, ans):
	min_points = 0
	min_moves = 0
	for i in diff.keys():
		(points, moves) = find(diff[i], c)
		min_points += points
		min_moves += moves
	ans.append((min_points, min_moves))

def main():
	t = int(input())
	ans = []
	for i in range(t):
		(n, c) = map(int, input().split())
		diff = {}
		for j in range(n):
			(x, y) = map(int, input().split())
			if x - y not in diff.keys():
				diff[x - y] = []
			diff[x - y].append((x, y))
		solve(diff, c, ans)
	for i in ans:
		print(i[0], i[1])
main()


t = int(input())
while t:
	t -= 1
	(n, c) = [int(x) for x in input().split()]
	d = {}
	while n:
		n -= 1
		(x, y) = [int(x) for x in input().split()]
		try:
			d[x - y, x % c].append(y)
		except:
			d[x - y, x % c] = [y]
	g = 0
	o = 0
	for i in d:
		g += 1
		l = d[i]
		l.sort()
		m = l[len(l) // 2]
		for j in l:
			o = o + abs(m - j) // c
	print(str(g) + ' ' + str(o))


for i in range(int(input())):
	(n, c) = map(int, input().split())
	d = {}
	for _ in range(n):
		(x, y) = map(int, input().split())
		if x - y in d:
			d[x - y].append(x)
		else:
			d[x - y] = []
			d[x - y].append(x)
	(a1, a2) = (0, 0)
	for j in d:
		(k, e, g) = (d[j], {}, [])
		for i in k:
			q = i % c
			if q in e:
				e[q].append(i)
			else:
				e[q] = [i]
				a1 += 1
				g.append(q)
		for i in g:
			k = e[i]
			k = sorted(k)
			q = len(k)
			if q % 2 != 0:
				z = k[q // 2]
				for w in k:
					a2 += abs(w - z) // c
			else:
				z = k[q // 2]
				y = k[q // 2 - 1]
				(r1, r2) = (0, 0)
				for w in k:
					r1 += abs(w - z) // c
					r2 += abs(w - y) // c
				a2 += min(r1, r2)
	print(a1, a2)


def help():
	(n, c) = map(int, input().split(' '))
	pts = []
	dicti = {}
	for i in range(n):
		(a, b) = map(int, input().split(' '))
		if dicti.get(a - b, -1) == -1:
			dicti[a - b] = [a]
		else:
			dicti[a - b].append(a)
		pts.append((a, b))
	check = 0
	operation = 0
	for line in dicti:
		ss = dicti[line]
		ll = len(dicti[line])
		dicti1 = {}
		for i in range(ll):
			key = ss[i] % c
			if dicti1.get(key, -1) == -1:
				dicti1[key] = [ss[i]]
			else:
				dicti1[key].append(ss[i])
		for seg in dicti1:
			check += 1
			ss2 = sorted(dicti1[seg])
			ll2 = len(ss2)
			mid = (ll2 - 1) // 2
			for i in range(ll2):
				operation += abs(ss2[i] - ss2[mid]) // c
	print(check, operation)
for _ in range(int(input())):
	help()