Chef received a permutation $P_1, P_2, \ldots, P_N$ and also an integer $D$ from his good friend Grux, because Grux was afraid he would forget them somewhere. However, since Grux was just playing with the permutation, it was all shuffled, and Chef only likes sorted permutations, so he decided to sort it by performing some swaps.
Chef wants to use the integer $D$ he just received, so he is only willing to swap two elements of the permutation whenever their absolute difference is exactly $D$. He has limited time, so you should determine the minimum number of swaps he needs to perform to sort the permutation, or tell him that it is impossible to sort it his way.

-----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 $D$.
- The second line contains $N$ space-separated integers $P_1, P_2, \ldots, P_N$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum number of swaps, or $-1$ if it is impossible to sort the permutation.

-----Constraints-----
- $1 \le T \le 20$
- $1 \le N \le 200,000$
- $1 \le D \le N$
- $1 \le P_i \le N$ for each valid $i$
- $P_1, P_2, \ldots, P_N$ are pairwise distinct
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (20 points): $D = 1$
Subtask #2 (30 points):
- $N \le 1,000$
- the sum of $N$ over all test cases does not exceed $10,000$
Subtask #3 (50 points): original constraints

-----Example Input-----
2
5 2   
3 4 5 2 1
5 2    
4 3 2 1 5  

-----Example Output-----
3
-1

-----Explanation-----
Example case 1: Chef can perform the following swaps in this order:
- swap the first and fifth element
- swap the third and fifth element
- swap the second and fourth element

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Data structures

Range queries

Segment trees revisited


Solutions:
t = int(input())

def solve(arr):
	if len(arr) == 1:
		return [0, arr]
	ans = 0
	left = arr[:len(arr) // 2]
	right = arr[len(arr) // 2:]
	(val1, lis1) = solve(left)
	(val2, lis2) = solve(right)
	(val, lis) = merge(lis1, lis2)
	return [val + val1 + val2, lis]

def merge(left, right):
	ans = []
	final = 0
	(i, j) = (0, 0)
	n = len(left)
	while i < len(left) and j < len(right):
		if left[i] < right[j]:
			ans += [left[i]]
			i += 1
		else:
			ans += [right[j]]
			final += n - i
			j += 1
	ans += left[i:] + right[j:]
	return [final, ans]
for _ in range(t):
	(n, d) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = 0
	dic = {i: [] for i in range(d)}
	found = False
	for i in range(n):
		if (arr[i] - i - 1) % d != 0:
			found = True
			break
		elif arr[i] % d == 0:
			dic[0] += [arr[i] // d - 1]
		else:
			dic[arr[i] % d] += [(arr[i] - arr[i] % d) // d]
	if found:
		print(-1)
	else:
		ans = 0
		for perm in list(dic.values()):
			ans += solve(perm)[0]
		print(ans)


import sys
sys.setrecursionlimit(10000000)

def mergeSortInversions(arr):
	if len(arr) == 1:
		return (arr, 0)
	larr = len(arr)
	a = arr[:larr // 2]
	b = arr[larr // 2:]
	(a, ai) = mergeSortInversions(a)
	(b, bi) = mergeSortInversions(b)
	c = []
	i = 0
	j = 0
	inversions = 0 + ai + bi
	la = len(a)
	while i < la and j < len(b):
		if a[i] <= b[j]:
			c.append(a[i])
			i += 1
		else:
			c.append(b[j])
			j += 1
			inversions += la - i
	c += a[i:]
	c += b[j:]
	return (c, inversions)
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	p = [int(o) for o in input().split()]
	array = [[] for i in range(d)]
	flag = 0
	for i in range(n):
		array[i % d].append(p[i])
		if p[i] % (i % d + 1) != 0:
			flag = 1
	ans = 0
	dumarr = [0] * n
	for i in range(d):
		(array[i], v) = mergeSortInversions(array[i])
		for j in range(len(array[i])):
			dumarr[i + j * d] = array[i][j]
		ans += v
	p = sorted(p)
	if dumarr == p:
		print(ans)
	else:
		print(-1)


def merge(arr, start, mid, end):
	p = start
	q = mid + 1
	k = 0
	inv = 0
	temp = [0] * len(arr)
	for i in range(start, end + 1):
		if p > mid:
			temp[k] = arr[q]
			k += 1
			q += 1
		elif q > end:
			temp[k] = arr[p]
			k += 1
			p += 1
		elif arr[p] <= arr[q]:
			temp[k] = arr[p]
			p += 1
			k += 1
		else:
			temp[k] = arr[q]
			q += 1
			k += 1
			inv += mid - p + 1
	for i in range(k):
		arr[start] = temp[i]
		start += 1
	return inv

def mergesort(arr, start, end):
	inv_count = 0
	if start < end:
		mid = (start + end) // 2
		inv_count += mergesort(arr, start, mid)
		inv_count += mergesort(arr, mid + 1, end)
		inv_count += merge(arr, start, mid, end)
	return inv_count

def solve():
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	inv_count = 0
	m = [0] * n
	sb = True
	for i in range(d):
		k = 0
		for j in range(i, n, d):
			m[k] = p[j]
			k += 1
		inv_count += mergesort(m, 0, k - 1)
		k = 0
		for j in range(i, n, d):
			if not m[k] == j + 1:
				sb = False
				break
			k += 1
	if sb:
		print(inv_count)
	else:
		print(-1)

def main():
	for _ in range(int(input())):
		solve()
main()


def getSum(BITree, index):
	sum = 0
	while index > 0:
		sum += BITree[index]
		index -= index & -index
	return sum

def updateBIT(BITree, n, index, val):
	while index <= n:
		BITree[index] += val
		index += index & -index

def getInvCount(arr, n):
	invcount = 0
	maxElement = max(arr)
	BIT = [0] * (maxElement + 1)
	for i in range(1, maxElement + 1):
		BIT[i] = 0
	for i in range(n - 1, -1, -1):
		invcount += getSum(BIT, arr[i] - 1)
		updateBIT(BIT, maxElement, arr[i], 1)
	return invcount
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	if k == 1:
		print(getInvCount(l, n))
		continue
	mat = l[:]
	f = 1
	sm = 0
	from collections import Counter
	for x in range(k):
		mat = []
		li = []
		le = 0
		for y in range(x, n, k):
			mat.append(l[y])
			li.append(y + 1)
			le += 1
		if Counter(mat) != Counter(li):
			f = 0
			break
		else:
			li = []
			le = len(mat)
			for i in range(le):
				curr = [mat[i], i]
				li.append(curr)
			li.sort()
			vis = [0] * le
			for i in range(le):
				if vis[i] or li[i][1] == i:
					continue
				c = 0
				j = i
				while not vis[j]:
					vis[j] = 1
					j = li[j][1]
					c += 1
				if c:
					sm += c - 1
	if f == 0:
		print(-1)
	else:
		print(sm)


def valid(hash_t, n, d):
	flag = 0
	for i in range(d):
		for j in range(i + 1, n, d):
			if (hash_t[j] - hash_t[i + 1]) % d != 0:
				flag = 1
				return False
	return True

def num_inversion(hash_t, n, d):
	count = 0
	for i in range(d):
		for j in range(i + 1, n, d):
			for k in range(j, n, d):
				if hash_t[j] > hash_t[k]:
					count += 1
	return count
tc = int(input())
while tc:
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	a = [int(x) for x in input().split(' ')]
	if d == 1:
		count = 0
		for i in range(n):
			for j in range(i + 1, n):
				if a[i] > a[j]:
					count += 1
		print(count)
	else:
		hash_t = [0] * (n + 1)
		for i in range(n):
			hash_t[a[i]] = i + 1
		if not valid(hash_t, n + 1, d):
			print(-1)
		else:
			count = num_inversion(hash_t, n + 1, d)
			print(count)
	tc -= 1


def merge(arr, start, mid, end):
	p = start
	q = mid + 1
	k = 0
	inv = 0
	temp = [0] * len(arr)
	for i in range(start, end + 1):
		if p > mid:
			temp[k] = arr[q]
			k += 1
			q += 1
		elif q > end:
			temp[k] = arr[p]
			k += 1
			p += 1
		elif arr[p] <= arr[q]:
			temp[k] = arr[p]
			p += 1
			k += 1
		else:
			temp[k] = arr[q]
			q += 1
			k += 1
			inv += mid - p + 1
	for i in range(k):
		arr[start] = temp[i]
		start += 1
	return inv

def mergesort(arr, start, end):
	inv_count = 0
	if start < end:
		mid = (start + end) // 2
		inv_count += mergesort(arr, start, mid)
		inv_count += mergesort(arr, mid + 1, end)
		inv_count += merge(arr, start, mid, end)
	return inv_count
for _ in range(int(input())):
	(n, d) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = [0] * len(p)
	for i in range(len(p)):
		a[p[i] - 1] = i
	m = []
	k = [i for i in range(n)]
	inv_count = 0
	for i in range(d):
		h = []
		for j in range(n):
			if i + j * d >= n:
				break
			h.append(a[i + j * d])
		m.append(h)
		inv_count += mergesort(m[-1], 0, len(m[-1]) - 1)
	s = [0] * n
	for i in range(d):
		for j in range(n):
			if i + j * d >= n:
				break
			s[i + j * d] = m[i][j]
	mb = True
	for i in range(n):
		if s[i] == k[i]:
			continue
		else:
			mb = False
			break
	if mb:
		print(inv_count)
	else:
		print(-1)


def merge(arr, temp, left, mid, right):
	inv_count = 0
	i = left
	j = mid
	k = left
	while i <= mid - 1 and j <= right:
		if arr[i] <= arr[j]:
			temp[k] = arr[i]
			k += 1
			i += 1
		else:
			temp[k] = arr[j]
			k += 1
			j += 1
			inv_count = inv_count + (mid - i)
	while i <= mid - 1:
		temp[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp[k] = arr[j]
		k += 1
		j += 1
	for i in range(left, right + 1, 1):
		arr[i] = temp[i]
	return inv_count

def _mergeSort(arr, temp, left, right):
	inv_count = 0
	if right > left:
		mid = int((right + left) / 2)
		inv_count = _mergeSort(arr, temp, left, mid)
		inv_count += _mergeSort(arr, temp, mid + 1, right)
		inv_count += merge(arr, temp, left, mid + 1, right)
	return inv_count

def countSwaps(arr, n):
	temp = [0 for i in range(n)]
	return _mergeSort(arr, temp, 0, n - 1)
for i in range(int(input())):
	(n, d) = map(int, input().split())
	a = [[] * i for i in range(d + 5)]
	p = list(map(int, input().split()))
	if d > 1:
		s = -1
		for i in p:
			s = (s + 1) % d
			a[s].append(i)
		ans = 0
		for i in a:
			ans = ans + countSwaps(i, len(i))
		i = -1
		f = [0] * n
		for i in range(len(a)):
			for j in range(len(a[i])):
				f[j * d + i] = a[i][j]
		p.sort()
		if f == p:
			print(ans)
		else:
			print('-1')
	else:
		print(countSwaps(p, len(p)))


def mergeSort(arr, n):
	temp_arr = [0] * n
	return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
	inv_count = 0
	if left < right:
		mid = (left + right) // 2
		inv_count = _mergeSort(arr, temp_arr, left, mid)
		inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
		inv_count += merge(arr, temp_arr, left, mid, right)
	return inv_count

def merge(arr, temp_arr, left, mid, right):
	i = left
	j = mid + 1
	k = left
	inv_count = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp_arr[k] = arr[i]
			k += 1
			i += 1
		else:
			temp_arr[k] = arr[j]
			inv_count += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp_arr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp_arr[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp_arr[loop_var]
	return inv_count

def solve():
	(n, d) = map(int, input().split())
	p = list(map(int, input().split()))
	inv_count = 0
	m = {}
	sb = True
	for i in range(d):
		k = 0
		for j in range(i, n, d):
			m[k] = p[j]
			k += 1
		inv_count += mergeSort(m, k)
		k = 0
		for j in range(i, n, d):
			if not m[k] == j + 1:
				sb = False
				break
			k += 1
	if sb:
		print(inv_count)
	else:
		print(-1)

def main():
	for _ in range(int(input())):
		solve()
main()


def mergeSort(arr, n):
	temp_arr = [0] * n
	return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
	inv_count = 0
	if left < right:
		mid = (left + right) // 2
		inv_count += _mergeSort(arr, temp_arr, left, mid)
		inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
		inv_count += merge(arr, temp_arr, left, mid, right)
	return inv_count

def merge(arr, temp_arr, left, mid, right):
	i = left
	j = mid + 1
	k = left
	inv_count = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp_arr[k] = arr[i]
			k += 1
			i += 1
		else:
			temp_arr[k] = arr[j]
			inv_count += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp_arr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp_arr[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp_arr[loop_var]
	return inv_count
t = int(input())
for _ in range(0, t):
	(n, D) = list([int(x) for x in input().split()])
	p = list([int(x) for x in input().split()])
	q = [0] * len(p)
	for i in range(n):
		q[p[i] - 1] = i
	sublists = []
	for i in range(0, D):
		sublist = []
		for j in range(i, len(p), D):
			sublist.append(q[j])
		sublists.append(sublist)
	flag = 0
	for i in range(0, D):
		temp_sublist = sorted(sublists[i])
		for j in range(0, len(sublists[i])):
			if i + j * D != temp_sublist[j]:
				print(-1)
				flag = 1
				break
		if flag == 1:
			break
	if flag == 0:
		total = sum([mergeSort(sublist, len(sublist)) for sublist in sublists])
		print(total)


def getSum(BITree, index):
	sum = 0
	while index > 0:
		sum += BITree[index]
		index -= index & -index
	return sum

def updateBIT(BITree, n, index, val):
	while index <= n:
		BITree[index] += val
		index += index & -index

def getInvCount(arr, n):
	invcount = 0
	maxElement = max(arr)
	BIT = [0] * (maxElement + 1)
	for i in range(1, maxElement + 1):
		BIT[i] = 0
	for i in range(n - 1, -1, -1):
		invcount += getSum(BIT, arr[i] - 1)
		updateBIT(BIT, maxElement, arr[i], 1)
	return invcount
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	f = 1
	sm = 0
	for x in range(k):
		mat = []
		li = []
		le = 0
		c = {}
		for y in range(x, n, k):
			mat.append(l[y])
			li.append(y + 1)
			le += 1
			c[l[y]] = 1
		for y in range(x, n, k):
			if c.get(y + 1, -1) == -1:
				f = 0
				break
		else:
			sm += getInvCount(mat, le)
	if f == 0:
		print(-1)
	else:
		print(sm)


def mergeSort(arr, n):
	temp_arr = [0] * n
	return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
	inv_count = 0
	if left < right:
		mid = (left + right) // 2
		inv_count = _mergeSort(arr, temp_arr, left, mid)
		inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
		inv_count += merge(arr, temp_arr, left, mid, right)
	return inv_count

def merge(arr, temp_arr, left, mid, right):
	i = left
	j = mid + 1
	k = left
	inv_count = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp_arr[k] = arr[i]
			k += 1
			i += 1
		else:
			temp_arr[k] = arr[j]
			inv_count += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp_arr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp_arr[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp_arr[loop_var]
	return inv_count

def findout(A, D):
	dic = {}
	for i in range(D):
		dic[i] = []
	for (i, x) in enumerate(A):
		dic[x % D] += [(i, x)]
	ans = 0
	for i in range(D):
		temp = dic[i]
		temp11 = []
		temp22 = []
		for (i, x) in temp:
			temp11 += [i]
			temp22 += [x]
		if sorted(temp11) != sorted(temp22):
			return -1
		temp33 = [0] * len(temp11)
		for (i, x) in temp:
			temp33[i // D] = x // D
		ans += mergeSort(temp33, len(temp33))
	return ans
for _ in range(int(input())):
	(N, K) = list(map(int, input().strip().split(' ')))
	A = list(map(int, input().strip().split(' ')))
	A = [x - 1 for x in A]
	print(findout(A, K))