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

Difficulty: interview

Starter code:

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


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


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


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


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)



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

# cook your dish here
for _ in range(int(input())):
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    x, suffix = 0, 0
    for i in range(n):
        for j in range(n):
            if arr[i] > arr[j]: x += 1
            if j > i:
                if arr[i] > arr[j]: suffix += 1
    print(x*( (k*(k-1))//2 ) + suffix*k)

# cook your dish here
for _ in range(int(eval(input()))):
    n, k = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    x, suffix = 0, 0
    for i, a_i in enumerate(arr):
        for a_j in arr:
            if a_i > a_j: x += 1
        for j in range(i+1, n):
            if a_i > arr[j]: suffix += 1
            
    ans = x*( (k*(k-1))//2 ) + suffix*k
    print(ans)

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


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)

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)

# cook your dish here
for i in range(int(input())):
    n,k=map(int,input().split())
    s=0
    a=0
    l=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)

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

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)

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)



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)



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)

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

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

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

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

#!/usr/bin/env python
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()