Almir had a small sequence $A_1, A_2, \ldots, A_N$. He decided to make $K$ copies of this sequence and concatenate them, forming a sequence $X_1, X_2, \ldots, X_{NK}$; for each valid $i$ and $j$ ($0 \le j < K$), $X_{j \cdot N + i} = A_i$.
For example, if $A = (1, 2, 3)$ and $K = 4$, the final sequence is $X = (1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3)$.
A pair $(i, j)$, where $1 \le i < j \le N$, is an inversion if $X_i > X_j$. Find the number of inversions in the final sequence $X$.

-----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 $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of inversions in the sequence $X$.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 100$
- $1 \le K \le 10^6$
- $1 \le A_i \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
3 3
2 1 3
4 100
99 2 1000 24

-----Example Output-----
12
30000

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(x, suffix) = (0, 0)
	for (i, a_i) in enumerate(arr):
		for (j, a_j) in enumerate(arr):
			if a_i > a_j:
				x += 1
			if j > i:
				if a_i > a_j:
					suffix += 1
	print(x * (k * (k - 1) // 2) + suffix * k)


T = int(input())
while T > 0:
	(N, K) = map(int, input().split())
	arr = []
	inp = input().split()
	for i in inp:
		arr.append(i)
	x = int(0)
	for i in range(0, N):
		for j in range(i + 1, N):
			if int(arr[i]) > int(arr[j]):
				x = x + 1
	y = int(0)
	for i in range(0, N):
		for j in range(i + 1, N):
			if int(arr[i]) < int(arr[j]):
				y = y + 1
	res = int((K + 1) * K * x * 0.5) + int((K - 1) * K * y * 0.5)
	print(res)
	T = T - 1


t = input()
t = int(t)

def merge_inv(arr, l, r):
	if l == r:
		return 0
	if r == l + 1:
		if arr[r] >= arr[l]:
			return 0
		else:
			(arr[r], arr[l]) = (arr[l], arr[r])
			return 1
	mid = (l + r) // 2
	inv1 = merge_inv(arr, l, mid)
	inv2 = merge_inv(arr, mid, r)
	merge = []
	i = l
	j = mid
	inv = 0
	while i < mid and j <= r:
		if arr[i] <= arr[j]:
			merge.append(arr[i])
			i += 1
		else:
			merge.append(arr[j])
			inv += mid - i
			j += 1
	if i >= mid:
		while j <= r:
			merge.append(arr[j])
			j += 1
	elif j > r:
		while i < mid:
			merge.append(arr[i])
			i += 1
	arr[l:r + 1] = merge
	return int(inv1 + inv2 + inv)
while t:
	t = t - 1
	n_k = input()
	n_k = n_k.split(' ')
	n = int(n_k[0])
	k = int(n_k[1])
	arr = input()
	arr = arr.split(' ')
	arr = list(map(int, arr))
	inv = merge_inv(arr, 0, n - 1)
	total_inv = inv * k
	num_small = [0]
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			ans = num_small[-1] + 1
		else:
			ans = num_small[-1]
		num_small.append(ans)
	sum_small = sum(num_small)
	total_inv += k * (k - 1) * sum_small / 2
	print(int(total_inv))


t = int(input())
for i in range(t):
	[N, K] = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	count = 0
	for i in range(N):
		for j in range(i + 1, N):
			if arr[i] > arr[j]:
				count += 1
	arr.sort()
	dict = {}
	for i in range(N):
		if arr[i] not in dict.keys():
			z = 0
			for j in range(N):
				if arr[j] > arr[i]:
					z += 1
			dict[arr[i]] = z
	ans = 0
	for i in range(N):
		ans += dict[arr[i]]
	ans = ans * K * (K - 1) // 2
	print(int(count * K + ans))


for T in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	C = [0, 0]
	for Z in range(2):
		L = N * (Z + 1)
		A *= Z + 1
		for I in range(L - 1):
			for J in range(I + 1, L):
				if A[I] > A[J]:
					C[Z] += 1
	print(C[0] + (K - 1) * (C[1] + (K - 1) * (C[1] - 2 * C[0])) // 2)


from math import *
from collections import *
from itertools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(1000000)
d = defaultdict(lambda : 0, {})

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

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

def o():
	return int(input())

def r(x):
	if type(x) == int:
		return range(x)
	else:
		return range(len(x))

def kl(con, x=0):
	if x == 0:
		print('Yes') if con else print('No')
	elif x == 1:
		print('yes') if con else print('no')
	elif x == 2:
		print('YES') if con else print('NO')
MOD = 1000000007
MAX = float('inf')
MIN = -float('inf')
p = input
for _ in r(o()):
	(n, k) = io()
	l = op()
	ans = 0
	for i in r(l):
		for j in r(l):
			if l[i] > l[j]:
				if i > j:
					ans += k * (k - 1) / 2
				elif i < j:
					ans += k * (k + 1) / 2
	print(int(ans))


def pos(i, n, list1):
	list2 = []
	res = 0
	for j in range(i, n):
		if list1[j] < list1[i]:
			list2.append(list1[j])
			res += 1
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list1 = [int(x) for x in input().split()]
	duplicate = list1.copy()
	list2 = []
	sum1 = 0
	duplicate.sort()
	for i in range(n):
		sum1 += k * (k - 1) // 2 * duplicate.index(list1[i]) + pos(i, n, list1) * k
	print(sum1)


import os
import sys

def main():
	t = int(input())
	while t > 0:
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		ll = sorted(l)
		count1 = 0
		for (i, val) in enumerate(ll):
			count1 = count1 + (i - ll[:i].count(val))
		ans = 0
		ans = ans + count1 * k * (k - 1) // 2
		count2 = 0
		for (i, val) in enumerate(l):
			temp = sum((1 for j in l[i + 1:] if j < val))
			count2 = count2 + temp
		ans = ans + count2 * k
		sys.stdout.write(str(ans) + '\n')
		t -= 1

def __starting_point():
	main()
__starting_point()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x1 = [0] * n
	for i in range(1, n):
		for j in range(i):
			if l[i] > l[j]:
				x1[i] += 1
	x2 = [0] * n
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i, -1):
			if l[i] > l[j]:
				x2[i] += 1
	res = 0
	for i in range(n):
		res += (k - 1) * k // 2 * x1[i] + (k + 1) * k // 2 * x2[i]
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	total = 0
	for i in range(n):
		current = arr[i]
		before = 0
		for j in arr[:i]:
			if j < current:
				before += 1
		after = 0
		for j in arr[i + 1:]:
			if j < current:
				after += 1
		num = before * k * (k - 1) // 2 + after * k * (k + 1) // 2
		total += num
	print(total)


def mergeSort(nums, count):
	if len(nums) == 1:
		return nums
	mid = len(nums) // 2
	a = mergeSort(nums[:mid], count)
	b = mergeSort(nums[mid:], count)
	a = merge(a, b, count)
	return a

def merge(a, b, count):
	ans = []
	j = len(a)
	s = len(b)
	pt1 = pt2 = 0
	c = 0
	while pt1 < j and pt2 < s:
		if a[pt1] <= b[pt2]:
			ans.append(a[pt1])
			pt1 += 1
			count[0] += c
			c = pt2
		else:
			ans.append(b[pt2])
			pt2 += 1
			c += 1
	while pt1 < j:
		ans.append(a[pt1])
		count[0] += len(b)
		pt1 += 1
	while pt2 < s:
		ans.append(b[pt2])
		pt2 += 1
	return ans
t = int(input())
for test in range(t):
	count = [0]
	(n, k) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	nums = mergeSort(nums, count)
	small = 0
	for i in range(n):
		for j in range(i + 1, n):
			if nums[i] < nums[j]:
				small += 1
	total = 0
	total += count[0] * k
	s = (k - 1) * (small + (k - 1) * small) // 2
	total += s
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n - 1):
		for j in range(i, n):
			if a[i] > a[j]:
				s += 1
	a.sort(reverse=True)
	s1 = 0
	for i in range(n - 1):
		for j in range(i, n):
			if a[i] > a[j]:
				s1 += 1
	print(k * s + s1 * (k * (k - 1)) // 2)


import sys
from math import gcd, sqrt, log, ceil, floor
tc = int(input().strip())
for t in range(tc):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = 0
	for i in range(n):
		(a, b) = (0, 0)
		for j in range(n):
			if arr[i] > arr[j]:
				if i > j:
					b += 1
				elif i < j:
					a += 1
		s += a * k * (k + 1) // 2 + b * k * (k - 1) // 2
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	ans = 0
	for i in range(n):
		(next, prev, temp) = (0, 0, 0)
		for j in range(i, n):
			if arr[i] > arr[j]:
				next += 1
		j = i
		while j >= 0:
			if arr[i] > arr[j]:
				prev += 1
			j -= 1
		temp = prev * k * (k - 1) / 2 + next * k * (k + 1) / 2
		ans += temp
	print(int(ans))


T = int(input(''))
for i in range(T):
	p = list(map(int, input().split()))
	n = p[0]
	k = p[1]
	A = list(map(int, input().split()))
	p = 0
	q = 0
	for i in range(n):
		for j in range(i, n):
			if A[i] > A[j]:
				p += 1
			elif A[i] < A[j]:
				q += 1
	print(int((p * k * (k + 1) + q * k * (k - 1)) / 2))


def a_sum(first, last, n):
	return (first + last) * n // 2

def inv_base(numbers):
	inv_count = 0
	for (i, ni) in enumerate(numbers):
		for (n, nj) in enumerate(numbers[i + 1:]):
			if ni > nj:
				inv_count += 1
	return inv_count

def inv_rep(n, k, numbers):
	d1 = inv_base(sorted(numbers, reverse=True))
	s = a_sum(0, (k - 1) * d1, k)
	return s

def inv_whole(n, k, numbers):
	return k * inv_base(numbers) + inv_rep(n, k, numbers)
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	numbers = [int(x) for x in input().split()]
	print(inv_whole(n, k, numbers))


t = int(input())
for jack in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	r1 = 0
	for i in range(n - 1):
		m = 0
		for j in range(i + 1, n):
			if a[i] > a[j]:
				m += 1
		r1 += m
	a.sort()
	(last, r2) = (0, 0)
	for i in range(n):
		if a[i] != a[i - 1]:
			r2 += i
			last = i
		else:
			r2 += last
	r = r1 * k + k * (k - 1) * r2 // 2
	print(r)


t = int(input())
for i in range(t):
	(n, u) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	x = []
	y = []
	for j in range(n):
		c = 0
		d = 0
		for k in range(n):
			if l[j] > l[k]:
				d = d + 1
			if l[j] > l[k] and j < k:
				c = c + 1
		y.append(d)
		x.append(c)
	ans = 0
	for j in range(len(x)):
		ans = ans + u / 2 * (2 * x[j] + (u - 1) * y[j])
	print(int(ans))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	effn = n * k
	c = 0
	for x in range(n):
		for y in range(n):
			if l[y] < l[x]:
				if y > x:
					a = (effn - y - 1) // n + 1
				else:
					a = (effn - y - 1) // n
				c += a * (a + 1) // 2
	print(c)


test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = [0] * n
	for i in range(n):
		for j in range(i, n):
			if arr[i] > arr[j]:
				res[i] += 1
	a1 = len(set(arr))
	a2 = a1 * (a1 - 1) // 2
	print(k * sum(res) + a2 * (k * (k - 1)) // 2)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	c = 0
	for i in range(N - 1):
		for j in range(i + 1, N):
			if A[i] > A[j]:
				X = K * (K + 1) // 2
				c += X
			elif A[i] < A[j]:
				X = K * (K - 1) // 2
				c += X
	print(c)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	num = list(map(int, input().split()))
	C = 0
	for i in range(N - 1):
		for j in range(i + 1, N):
			if num[i] > num[j]:
				S = K * (K + 1) // 2
				C = C + S
			elif num[i] < num[j]:
				S = K * (K - 1) // 2
				C = C + S
	print(C)


def sree(k, n, m):
	sum1 = m * (m + 1) // 2
	sum2 = m * (m - 1) // 2
	shanth = 0
	for i in range(n):
		count = 0
		for j in range(n):
			if i < j and k[i] > k[j]:
				shanth += sum1
			elif j < i and k[i] > k[j]:
				shanth += sum2
	return shanth
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	k = list(map(int, input().split()))
	print(sree(k, n, m))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	arr1 = [0] * n
	arr2 = [0] * n
	i = 0
	while i < n:
		for j in range(i + 1, n):
			if l[j] < l[i]:
				arr2[i] += 1
		i += 1
	i = 0
	while i < n:
		for j in range(n):
			if l[j] < l[i]:
				arr1[i] += 1
		i += 1
	ans = 0
	for i in range(n):
		ans += int(k / 2 * (2 * arr2[i] + (k - 1) * arr1[i]))
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	invCount = 0
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				invCount += 1
	ans = k * invCount
	for i in range(n):
		smallNo = 0
		for j in range(n):
			if arr[j] < arr[i]:
				smallNo += 1
		ans += k * (k - 1) // 2 * smallNo
	print(ans)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		all = 0
		rg = 0
		for j in range(0, i):
			if a[j] < a[i]:
				all += 1
		for j in range(i + 1, n):
			if a[j] < a[i]:
				all += 1
				rg += 1
		ans += int(all * (k * (k - 1) / 2))
		ans += int(rg * k)
	print(ans)
	t -= 1


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = []
	y = []
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				x.append([i, j])
		for z in range(0, i):
			if a[i] > a[z]:
				y.append([i, z])
	print(((k * k + k) * len(x) + (k * k - k) * len(y)) // 2)


import sys
import math
from collections import defaultdict

def fout(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fin():
	return sys.stdin.readline().strip()
mod = pow(10, 9) + 7
t = int(fin())
while t > 0:
	t -= 1
	(n, k) = map(int, fin().split())
	a = [int(x) for x in fin().split()]
	ans = 0
	for i in range(n):
		c = 0
		for j in range(i):
			if a[i] < a[j]:
				c += 1
		ans += k * c
		for j in range(i + 1, n):
			if a[j] > a[i]:
				c += 1
		ans += k * (k - 1) * c // 2
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	pairs = 0
	tot = ((k - 1) ** 2 + (k - 1)) // 2
	for i in range(n):
		less = len([f for f in a[:i] if f > a[i]])
		alls = len([g for g in a if g > a[i]])
		pairs += k * less + alls * tot
	print(pairs)


T = int(input())
for _ in range(T):
	(n, k) = tuple(map(int, input().split()))
	seq = list(map(int, input().split()))
	totInv = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if seq[i] < seq[j]:
				totInv += (k - 1) * k // 2
			elif seq[i] > seq[j]:
				totInv += k * (k + 1) // 2
			else:
				continue
	print(totInv)


import math

def solve(input_array, k):
	out = 0
	k_fact = k * (k + 1) / 2
	for (i, x) in enumerate(input_array):
		ci = 0
		coi = 0
		for (j, y) in enumerate(input_array):
			if x > y:
				ci += 1
				if j < i:
					coi += 1
		ans = k_fact * ci - coi * k
		out = out + ans
	return int(out)
t = int(input())
for r in range(1, t + 1):
	(n, k) = list(map(int, input().split(' ')))
	input_array = list(map(int, input().split(' ')))
	result = solve(input_array, k)
	print(result)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	inv = 0
	smallbeforeMe = [0] * n
	smallafterMe = [0] * n
	largebeforeMe = [0] * n
	largeafterMe = [0] * n
	for i in range(n):
		for j in range(n):
			if a[i] > a[j]:
				if i > j:
					smallbeforeMe[i] += 1
				else:
					smallafterMe[i] += 1
			if a[i] < a[j]:
				if i > j:
					largebeforeMe[i] += 1
				else:
					largeafterMe[i] += 1
	print(sum(list(map(lambda x: x * (k * (k + 1) // 2), smallafterMe)) + list(map(lambda x: x * (k * (k - 1) // 2), smallbeforeMe))))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				count += k * (k + 1) // 2
			elif a[i] < a[j]:
				count += k * (k - 1) // 2
	print(count)
	t -= 1


t = int(input())
while t:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = [int(x) for x in input().split()]
	inv = {}
	for i in range(n):
		c = 0
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				c += 1
		inv[arr[i]] = c
	arr.sort()
	sm = [0]
	ele = 0
	for i in range(1, n):
		if arr[i - 1] < arr[i]:
			ele += 1
		sm.append(ele)
	fn = 0
	for i in range(0, n):
		x = inv[arr[i]]
		if x < 0:
			x = 0
		fn += k * (2 * x + (k - 1) * sm[i]) / 2
	print(int(fn))
	t -= 1


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		A = [int(i) for i in input().split()]
		res = 0
		for i in range(len(A)):
			cnt1 = 0
			cnt2 = 0
			for j in range(len(A)):
				if i < j:
					if A[i] < A[j]:
						cnt1 += 1
				if i > j:
					if A[i] < A[j]:
						cnt2 += 1
			res += cnt1 * k * (k - 1) // 2
			res += cnt2 * k * (k + 1) // 2
		print(res)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	t = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				t += 1
	v = 0
	g = k * (k - 1) // 2
	a.sort()
	t = t * k
	for i in a:
		t += a.index(i) * g
	print(t)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	ans = 0
	for i in range(0, n):
		t = int(0)
		y = int(0)
		for r in range(0, i):
			if a[r] < a[i]:
				t += 1
		for j in range(i, n):
			if a[i] > a[j]:
				y += 1
		ans += (2 * y + (t + y) * (k - 1)) * k / 2
	print(int(ans))


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	x = 0
	for i in range(N - 1):
		for j in range(i + 1, N):
			if A[i] > A[j]:
				x += 1
	y = []
	for i in range(N):
		z = 0
		for j in range(N):
			if A[i] > A[j]:
				z += 1
		y.append(z)
	if K == 1:
		print(x)
	else:
		print(x * K + sum(y) * K * (K - 1) // 2)


import math

def countInversions(arr, n):
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				count += 1
	return count

def answer_finder():
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	inversions = countInversions(arr, n)
	answer = 0
	answer += inversions * k
	for i in range(n):
		rem_count = 0
		for j in range(n):
			if arr[i] > arr[j]:
				rem_count += 1
		answer += math.floor(k * (k - 1) / 2) * rem_count
	print(answer)
test_cases = int(input())
while test_cases:
	test_cases -= 1
	answer_finder()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	s = ap = 0
	for i in range(len(l)):
		c1 = c2 = 0
		for j in range(len(l)):
			if l[i] > l[j]:
				c1 += 1
				if i < j:
					c2 += 1
		l1.append(c1)
		l2.append(c2)
	for i in range(len(l1)):
		if l1[i] == l2[i]:
			x = l1[i] * k
			ap = k / 2 * (2 * x + (k - 1) * -l1[i])
			s += ap
		else:
			x = l1[i] * (k - 1) + l2[i]
			ap = k / 2 * (2 * x + (k - 1) * -l1[i])
			s += ap
	print(int(s))


tn = int(input())
for _ in range(tn):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	di1 = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				di1[i] += 1
	s1 = len(set(arr))
	s2 = s1 * (s1 - 1) // 2
	print(k * sum(di1) + s2 * (k * (k - 1)) // 2)


def main():
	for _ in range(int(input())):
		(N, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		res = 0
		for i in range(N):
			v = arr[i]
			for j in range(i):
				if arr[j] < v:
					res += (k - 1) * k // 2
			for j in range(i + 1, N):
				if arr[j] < v:
					res += k * (k + 1) // 2
		print(res)
main()


t = int(input())
for i in range(t):
	(n, k) = tuple(map(int, input().split()))
	l = list(map(int, input().split()))[:n]
	ct = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if l[i] > l[j]:
				ct = ct + k * (k + 1) // 2
			elif l[i] < l[j]:
				ct = ct + k * (k - 1) // 2
			else:
				continue
	print(ct)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	count1 = 0
	for i in range(n):
		for j in range(i + 1, n):
			if list1[i] > list1[j]:
				count1 += k * (k + 1) // 2
			elif list1[i] < list1[j]:
				count1 += k * (k - 1) // 2
	print(count1)
	t -= 1


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	ll = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	for i in range(N):
		for j in range(i + 1, N):
			if ll[i] > ll[j]:
				c1 += 1
	for i in range(N):
		for j in range(N):
			if ll[i] > ll[j]:
				c2 += 1
	print(c1 * K + c2 * K * (K - 1) // 2)


for i in range(int(input())):
	x = 0
	y = 0
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		for j in range(i, n):
			if a[i] > a[j]:
				x = x + 1
			elif a[j] > a[i]:
				y = y + 1
	print(x * k * (k + 1) // 2 + y * k * (k - 1) // 2)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = [0] * n
	ans2 = [0] * n
	for i in range(n):
		for j in range(n):
			if i < j and arr[i] > arr[j]:
				ans[i] = ans[i] + 1
			if i > j and arr[i] > arr[j]:
				ans2[i] = ans2[i] + 1
	for i in range(n):
		if ans[i] != 0:
			ans[i] = ans[i] * k * (k + 1) // 2
		if ans2[i] != 0:
			ans2[i] = ans2[i] * k * (k - 1) // 2
	print(sum(ans) + sum(ans2))


t = int(eval(input()))
for i in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	k = inp[1]
	inp = list(map(int, input().split()))
	before = []
	after = []
	ans = 0
	for p in range(len(inp)):
		bef_count = 0
		af_count = 0
		for q in range(len(inp)):
			if q > p and inp[q] < inp[p]:
				af_count += 1
			elif q < p and inp[q] < inp[p]:
				bef_count += 1
		ans += af_count * (k * (k + 1)) // 2
		ans += bef_count * (k * (k - 1)) // 2
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(N):
		for j in range(i, N):
			if arr[i] > arr[j]:
				ans += 1
	ans *= K
	temp = N * N
	for x in arr:
		temp -= arr.count(x)
	temp = temp * K * (K - 1) // 4
	ans += temp
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	s = 0
	for i in range(n):
		(a, b) = (0, 0)
		for j in range(n):
			if arr[i] > arr[j]:
				if i > j:
					b += 1
				elif i < j:
					a += 1
		s += a * k * (k + 1) // 2 + b * k * (k - 1) // 2
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cross_inversion = 0
	auto_inversion = 0
	for i in range(n):
		for j in range(n):
			if a[i] > a[j]:
				cross_inversion += 1
				if i < j:
					auto_inversion += 1
	total_inversions = k * auto_inversion + k * (k - 1) // 2 * cross_inversion
	print(total_inversions)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	(s, a, l) = (0, 0, list(map(int, input().split())))
	l2 = 2 * l
	for i in range(n - 1):
		for j in range(i + 1, n):
			if l[i] > l[j]:
				a += 1
	for i in range(n):
		for j in range(n, 2 * n):
			if l2[i] > l2[j]:
				s += 1
	print(k * (k - 1) // 2 * s + k * a)


for _ in range(int(input())):
	(nd, kd) = map(int, input().split())
	ad = list(map(int, input().split()))
	td = 0
	for i in range(nd):
		for j in range(i + 1, nd):
			if ad[i] > ad[j]:
				td += 1
	vd = 0
	gd = kd * (kd - 1) // 2
	ad.sort()
	td = td * kd
	for i in ad:
		td += ad.index(i) * gd
	print(td)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	(c, d) = (0, 0)
	for i in range(n):
		for j in range(i + 1, n):
			if x[i] > x[j]:
				c += 1
			if x[i] < x[j]:
				d += 1
	ans = (k + 1) * k * c // 2 + (k - 1) * k * d // 2
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	(l, r) = (0, 0)
	for i in range(N):
		for j in range(i):
			if A[i] > A[j]:
				l += 1
		for j in range(i + 1, N):
			if A[i] > A[j]:
				r += 1
	print(l * K * (K - 1) // 2 + r * K * (K + 1) // 2)


a = int(input())
for i in range(a):
	[N, K] = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	count = 0
	for i in range(N):
		for j in range(i + 1, N):
			if arr[i] > arr[j]:
				count += 1
	arr.sort()
	dict = {}
	for i in range(N):
		if arr[i] not in dict.keys():
			z = 0
			for j in range(N):
				if arr[j] > arr[i]:
					z += 1
			dict[arr[i]] = z
	answer = 0
	for i in range(N):
		answer += dict[arr[i]]
	answer = answer * K * (K - 1) // 2
	print(int(count * K + answer))


def main():
	t = int(input())
	while t > 0:
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		ll = sorted(l)
		count1 = 0
		for (i, val) in enumerate(ll):
			count1 = count1 + (i - ll[:i].count(val))
		ans = 0
		ans = ans + count1 * k * (k - 1) // 2
		count2 = 0
		for (i, val) in enumerate(l):
			temp = sum((1 for j in l[i + 1:] if j < val))
			count2 = count2 + temp
		ans = ans + count2 * k
		print(ans)
		t -= 1

def __starting_point():
	main()
__starting_point()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	t = []
	p = []
	c = 0
	o = m * (m - 1) // 2
	s = sorted(l)
	for i in range(n):
		t.append(s.index(l[i]))
		p.append(sorted(l[i:]).index(l[i]))
		c += t[i] * o + m * p[i]
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	inv = 0
	for i in range(len(A)):
		for j in range(i + 1, len(A)):
			if A[i] > A[j]:
				inv += 1
	ans = k * inv
	smallcount = 0
	for i in range(len(A)):
		for j in range(len(A)):
			if A[i] > A[j]:
				smallcount += 1
	ans += k * (k - 1) // 2 * smallcount
	print(ans)


import sys
input = sys.stdin.readline

def first(l, k):
	nb = 0
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			if l[j] < l[i]:
				nb += 1
	return nb * k

def second(l, k):
	out = []
	res = 0
	for i in range(len(l)):
		nb = 0
		for j in range(len(l)):
			if l[j] < l[i]:
				nb += 1
		res += nb * k * (k - 1) // 2
		out.append(nb)
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	firs = first(a, k)
	l = second(a, k)
	print(l + firs)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m1 = []
	n1 = []
	for i in range(n - 1):
		co = 0
		for j in range(i + 1, n):
			if l[i] > l[j]:
				co += 1
		m1.append(co)
	m1.append(0)
	for i in range(n):
		co = 0
		for j in range(n):
			if l[i] > l[j]:
				co += 1
		n1.append(co)
	ans = 0
	for i in range(n):
		(p1, p2) = (m1[i], n1[i])
		import math
		k1 = k / 2 * (2 * p1 + (k - 1) * p2)
		ans += int(k1)
	print(ans)


from bisect import bisect_left

def count(nums):
	res = []
	seq = sorted(nums)
	for num in nums:
		pos = bisect_left(seq, num)
		res.append(pos)
		seq.pop(pos)
	return sum(res)
for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	nums = list(map(int, input().split(' ')))
	inv = count(nums)
	smaller = 0
	for i in range(len(nums)):
		for j in range(len(nums)):
			if nums[i] > nums[j]:
				smaller += 1
	tinv = k * (k - 1) / 2 * smaller + k * inv
	print(int(tinv))


t = int(input())
while t > 0:
	x = 0
	y = 0
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	for i in range(n):
		for j in range(i, n):
			if a[i] > a[j]:
				x = x + 1
			elif a[j] > a[i]:
				y = y + 1
	print(x * k * (k + 1) // 2 + y * k * (k - 1) // 2)
	t = t - 1


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	ar = [int(i) for i in input().split()]
	c1 = 0
	c2 = 0
	for i in range(0, n):
		for j in range(i + 1, n):
			if ar[i] > ar[j]:
				c1 += 1
	c1 = c1 * k
	for i in range(0, n):
		for j in range(0, n):
			if ar[i] > ar[j]:
				c2 += 1
	c2 = c2 * k * (k - 1) // 2
	print(c1 + c2)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = list(set(arr))
	s.sort(reverse=True)
	c = 0
	c1 = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				c += 1
		for j in range(i - 1, -1, -1):
			if arr[j] < arr[i]:
				c1 += 1
	i += 1
	for j in range(i - 1, -1, -1):
		if arr[j] < arr[i]:
			c1 += 1
	x = c * k * (k + 1) // 2
	y = c1 * k * (k - 1) // 2
	print(x + y)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	total = []
	after = []
	for i in range(n):
		c = 0
		for j in range(i + 1, n):
			if a[i] > a[j]:
				c += 1
		after.append(c)
		for j in range(i):
			if a[i] > a[j]:
				c += 1
		total.append(c)
	c = 0
	for i in range(n):
		c += (k - 1) * k * total[i] // 2 + k * after[i]
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	num = list(map(int, input().split()))
	sum = 0
	for i in range(1, n + 1):
		c = num[i - 1]
		count_for = 0
		count_bac = 0
		for j in range(i, n):
			if num[j] < c:
				count_for += 1
		for j in range(i):
			if num[j] < c:
				count_bac += 1
		count = count_for + count_bac
		p = k * (k + 1) // 2 * count
		p = p - k * count_bac
		sum = sum + p
	print(sum)


def count(k, n, m):
	sum1 = m * (m + 1) // 2
	sum2 = m * (m - 1) // 2
	ct = 0
	for i in range(n):
		for j in range(n):
			if i < j and k[i] > k[j]:
				ct += sum1
			elif j < i and k[i] > k[j]:
				ct += sum2
	return ct
test = int(input())
for _ in range(test):
	(n, m) = map(int, input().split())
	k = list(map(int, input().split()))
	print(count(k, n, m))


t = int(input())
for i in range(0, t):
	a = list(map(int, input().split()))
	n = a[0]
	k = a[1]
	one = 0
	two = 0
	a = list(map(int, input().split()))
	for i in range(0, n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				one = one + 1
			elif a[i] < a[j]:
				two = two + 1
	ans = k * (one * (k + 1) + two * (k - 1)) / 2
	print(int(ans))


t = int(input())
for _ in range(t):
	(n, rep) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(len(a)):
		l = 0
		r = 0
		for j in range(i, -1, -1):
			if a[j] < a[i]:
				l += 1
		for j in range(i, n, 1):
			if a[j] < a[i]:
				r += 1
		tot = l + r
		lt = tot * (rep - 1) + r
		ans += rep / 2.0 * (r + lt)
	print(int(ans))


def getSum(v):
	return v * (v - 1) // 2
tn = int(input())
for _ in range(tn):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s1 = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				s1 += 1
	s2 = getSum(len(set(arr)))
	print(k * s1 + s2 * getSum(k))


def soln(n, k, arr):
	a = [0] * n
	d = [0] * n
	for i in range(n):
		a_count = total = 0
		for j in range(i + 1, i + n):
			cur = arr[j % n]
			if cur < arr[i]:
				if j < n:
					a_count += 1
				total += 1
		a[i] = a_count
		d[i] = total
	res = 0
	for i in range(n):
		res += k * (2 * a[i] + (k - 1) * d[i]) // 2
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(soln(n, k, arr))


import sys
from random import choice, randint
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	t = I()
	l = []
	for _ in range(t):
		(n, k) = MI()
		a = LI()
		lcf = [0] * n
		lce = [0] * n
		for i in range(n):
			(cnt1, cnt2) = (0, 0)
			for j in a[:i]:
				if j < a[i]:
					cnt1 += 1
			for j in a[i:]:
				if j < a[i]:
					cnt2 += 1
			lcf[i] = cnt1
			lce[i] = cnt2
		ans = 0
		for i in range(n):
			ans += lcf[i] * (k * (k - 1) // 2)
		for i in range(n):
			ans += lce[i] * (k * (k + 1) // 2)
		l.append(ans)
	for i in range(t):
		pf(str(l[i]))

def __starting_point():
	main()
__starting_point()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if l[i] > l[j]:
				x = k * (k + 1) // 2
				c += x
			elif l[i] < l[j]:
				x = k * (k - 1) // 2
				c += x
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(len(arr)):
		for j in range(i):
			if arr[j] > arr[i]:
				ans += 1
	sarr = sorted(arr, reverse=True)
	tans = 0
	for i in range(1, len(sarr)):
		if sarr[i - 1] != sarr[i]:
			tans += i
	k -= 1
	print(ans * (k + 1) + tans * (k * (k + 1) // 2))


case = int(input())
for _ in range(case):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	inv = {}
	for i in range(n):
		count = 0
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				count += 1
		inv[arr[i]] = count
	arr.sort()
	smaller = [0]
	elem = 0
	for i in range(1, n):
		if arr[i - 1] < arr[i]:
			elem += 1
		smaller.append(elem)
	res = 0
	for i in range(n):
		d = smaller[i]
		a = inv[arr[i]]
		res += k / 2 * (2 * a + (k - 1) * d)
	print(int(res))


def inversions(a):
	lower = [0 for _ in a]
	upper = [0 for _ in a]
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if a[i] > a[j]:
				upper[i] += 1
		for j in range(i):
			if a[i] > a[j]:
				lower[i] += 1
	return (lower, upper)
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	(low, upp) = inversions(a)
	num = 0
	for i in range(n):
		num += k * (k + 1) // 2 * upp[i]
		num += (k - 1) * k // 2 * low[i]
	print(num)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	a = list(map(int, input().split()))
	for (i, e) in enumerate(a):
		left = right = 0
		for j in range(n):
			if a[j] < e and j < i:
				left += 1
			elif a[j] < e and j > i:
				right += 1
		leftres = k * (k - 1) * left // 2
		rightres = k * (k + 1) * right // 2
		ans += leftres + rightres
	print(ans)


import math
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	s = 0
	for i in range(N):
		cs = 0
		for j in range(N):
			if A[j] < A[i] and i != j:
				cs += 1
				if j > i:
					s += K
		s += cs * K * (K - 1) / 2
	print(int(s))


def swap(arr, x, y):
	t = arr[x]
	arr[x] = arr[y]
	arr[y] = t
	return arr
t = int(input())
while t > 0:
	t -= 1
	ip = input().split()
	(n, k) = [int(x) for x in ip]
	ip = input().split()
	a = [int(x) for x in ip]
	b = [x for x in a]
	cnt = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				cnt += 1
			if b[i] > b[j]:
				b = swap(b, i, j)
	q = k * (k - 1) // 2
	cnt1 = 0
	x = 0
	for i in range(n - 1):
		if b[i] == b[i + 1]:
			x += 1
		else:
			x += 1
			cnt1 += (n - i - 1) * x
			x = 0
	print(k * cnt + q * cnt1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	p = len(set(l))
	s = 0
	for i in range(n - 1):
		for j in range(i, n):
			if l[i] > l[j]:
				s += 1
	s1 = 0
	l.sort(reverse=True)
	for i in range(n - 1):
		for j in range(i, n):
			if l[i] > l[j]:
				s1 += 1
	base = k * s + k * (k - 1) // 2 * s1
	print(base)


import sys
from math import gcd, sqrt, ceil, log

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	(n, k) = li()
	a = li()
	inv = 0
	for j in range(n):
		for i in range(j):
			if a[i] > a[j]:
				inv += k * (k + 1) // 2
			if a[i] < a[j]:
				inv += k * (k - 1) // 2
	print(inv)