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: interview

Starter code:

Solutions:
t = int(input())

for i in range(t):
 n, c = list(map(int,input().split()))

 pts = {}
 moves = 0

 for i in range(n):
  x, y = list(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)


   




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)

# cook your dish here
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)

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)

import collections
t=int(input())
for _ in range(t):
 n,c=list(map(int,input().split()))
 hashmap=collections.defaultdict(list)
 for i in range(n):
  x,y=list(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)


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)

# cook your dish here

t = int(input())
for _ in range(t):
 n, c = list(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])
   #print(grp)
   med = grp[int(len(grp)/2)]
   #print(med)
   for i in range(len(grp)):
    nop += abs(grp[i] - med)//c
  group.clear()
 print(noc,nop)
   
    



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])
 # print(d)
 e = []
 for i in d.values():
  e.append(i)
 # print(a)
 # print(e)
 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)
  # print(g)

 c = 0
 print(len(g), end=" ")
 for i in range(len(g)):
  # print(1)
  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


# cook your dish here
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))
  #cont[ (x-y,(x%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)


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 list(D.values()):
  L=k
  L.sort()
  w=len(L)
  A=L[:(w)//2]
  #we want to exclude a point
  B=L[(w+1)//2:]
  #understang this by appling it in copy
  p+=sum(B)-sum(A)
 print(q,p)


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 list(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)


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)


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()
   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))
    moves += choice1
 print(numpoints, moves)


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()
   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 += choice1
 print(numpoints, moves)


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()
   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(numpoints, moves)


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)


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 list(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)


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)

#from statistics import median
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)
 
 #print(hh)        
 opr = 0 

 for j in hh:

  arr = hh[j]
  #print(arr)
  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))


# cook your dish here
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()))

# cook your dish here
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]]
 #print(dict1)
 
 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
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)