The ugliness of a sequence of size N is defined as the number of pairs of neighboring elements which are not equal to each other. Formally, the ugliness of a sequence increase by 1 if for a value of i, 2 ≤ i ≤ N, the following condition holds true:
A_{i} \neq A_{i-1}.

Examples: 
[1, 2, 2, 3], ugliness is 2.
[2, 1, 2, 3,4], ugliness is 4.

You are given a sequence A of length N consisting of the first K natural numbers only. Each of the first K natural numbers occur at least once in the given sequence. For each value of K, you are supposed to remove all of its occurrences from the original sequence and determine the ugliness of the resulting sequence.

Note:  An empty sequence has ugliness of 0.

------ Input Format ------ 

- First line will contain T, the number of test cases. Then the testcases follow.
- Each testcase consist of two lines of input
- First line contains two integers N, K 
- Second line contains N space-separated integers, where the i^{th} integer denotes the i^{th} element of the sequence A.

------ Output Format ------ 

- For each testcase print K space-separated integers denoting the answer for that testcase.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ K ≤ N ≤ 10^{5}$
- For each $i$, $1 ≤ A_{i} ≤ K$
- Every number from $1$ to  $K$ appears atleast once
- Sum of N over all cases doesn't exceed $10^{5}$

----- Sample Input 1 ------ 
2
8 2
1 2 1 2 2 2 1 2
8 3
1 2 2 1 1 1 2 3
----- Sample Output 1 ------ 
0 0
1 1 3

----- explanation 1 ------ 
Test case 1:
- By removing 1, we get the sequence: $[2, 2, 2, 2, 2]$. Since all the elements are the same, ugliness is $0$
- By removing 2, we get the sequence: $[1, 1, 1]$. Since all the elements are the same, ugliness is $0$

Test case 2:
- By removing 1, we get the sequence: $[2, 2, 2, 3]$. Since the 3rd and 4th elements are not equal, ugliness is $1$.
- By removing 2, we get the sequence: $[1, 1, 1, 1, 3]$. Since the 3rd and 4th elements are not equal, ugliness is $1$.
- By removing 3, we get the sequence: $[1, 2, 2, 1, 1, 1, 2]$. Since 1st and 2nd, 3rd and 4th, 6th and 7th are not equal, total ugliness is $3$.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Data structures
Skill types: Data structures

Starter code:

Solutions:
from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 1:
		print(0)
		continue
	temp = []
	temp.append(arr[0])
	total_ugliness = 0
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			temp.append(arr[i + 1])
			total_ugliness += 1
	leni = len(temp)
	dic = defaultdict(int)
	for i in range(1, leni - 1):
		if temp[i - 1] != temp[i + 1]:
			dic[temp[i]] += 1
		else:
			dic[temp[i]] += 2
	dic[temp[0]] += 1
	dic[temp[-1]] += 1
	for i in range(1, k + 1):
		ans = total_ugliness - dic[i]
		print(ans, end=' ')
	print()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	v = {}
	for i in range(1, k + 1):
		v[i] = 0
	b = [int(x) for x in input().split()]
	if k == 1:
		print(0)
		continue
	c = []
	x = -1
	for i in range(n):
		if b[i] != x:
			c.append(b[i])
			x = b[i]
	t = len(c) - 1
	for j in range(len(c)):
		if j == 0:
			v[c[j]] += 1
		elif j == len(c) - 1:
			v[c[j]] += 1
		elif c[j - 1] == c[j + 1]:
			v[c[j]] += 2
		else:
			v[c[j]] += 1
	for j in v.keys():
		print(t - v[j], end=' ')
	print()


from sys import stdin
rline = stdin.readline
rfile = stdin.read

def rt(tip=int):
	return tip(rline())

def rts(tip=int, way=rline):
	return [tip(v) for v in way().split()]

def solve():
	T = rt()
	while T > 0:
		T -= 1
		(N, K) = rts()
		A = []
		p = -1
		for v in rts():
			if v != p:
				A.append(v)
				p = v
		N = len(A)
		born_after_remove = [0] * (K + 1)
		current = [0] * (K + 1)
		S = 0
		for n in range(N - 1):
			if n > 0:
				born_after_remove[A[n]] += A[n - 1] != A[n + 1]
			current[A[n]] += 1
			current[A[n + 1]] += 1
			S += 2
		ret = [0] * (K + 1)
		for k in range(1, K + 1):
			ret[k] = (S - 2 * current[k]) // 2 + born_after_remove[k]
		print(' '.join((str(ret[k]) for k in range(1, K + 1))))
solve()


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
for _ in range(int(input())):
	(n, k) = mul()
	t = seq()
	if k == 1:
		print(0)
		continue
	l = []
	m = [0] * (k + 1)
	x = -1
	for i in range(n):
		if t[i] != x:
			l.append(t[i])
			x = t[i]
	u = len(l) - 1
	c = Counter(l)
	for i in range(1, len(l) - 1):
		x = l[i]
		if l[i - 1] == l[i + 1]:
			m[x] += 1
	for i in range(1, k + 1):
		print(u - m[i] - c[i], end=' ')
	print()


import sys
for _ in range(int(sys.stdin.readline())):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	case = list(map(int, sys.stdin.readline().split()))
	if k == 1:
		print(0)
		continue
	prev = -1
	arr = []
	ugly = -1
	for c in case:
		if c != prev:
			arr.append(c)
			prev = c
			ugly += 1
	out = [ugly] * k
	for a in range(len(arr)):
		before = arr[a - 1]
		now = arr[a]
		if a + 1 == len(arr):
			nex = arr[0]
		else:
			nex = arr[a + 1]
		if a == 0 or a == len(arr) - 1:
			out[now - 1] -= 1
		elif before == nex:
			out[now - 1] -= 2
		else:
			out[now - 1] -= 1
	sys.stdout.write(str(' '.join(list(map(str, out)))) + '\n')


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(k):
		d[i + 1] = [0, 0]
	l = -1
	c = 0
	for i in range(n - 1):
		if A[i] != A[i + 1]:
			if l == A[i + 1]:
				d[A[i]][1] += 1
			else:
				d[A[i]][0] += 1
			c += 1
			l = A[i]
	if c >= 1:
		d[A[-1]][0] += 1
	ans = []
	for i in range(k):
		ans.append(c - d[i + 1][0] - d[i + 1][1] * 2)
	print(*ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	prev = -1
	now = -1
	next = -1
	same = 0
	value = [0] * k
	for i in range(n - 1):
		index = n - i - 1
		now = l[index]
		next = l[index - 1]
		if prev != -1 and prev != next and (next != now) and (now != prev):
			value[now - 1] -= 1
		if now != next:
			value[now - 1] += 1
			value[next - 1] += 1
			prev = now
		else:
			same += 1
	for i in value:
		print(n - i - 1 - same, end=' ')
	print()


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split())) + ['#']
	B = ['#']
	for i in range(1, N + 1):
		if A[i] != A[i - 1]:
			B.append(A[i - 1])
	B.append('#')
	ht = {}
	for i in range(1, len(B) - 1):
		if B[i] not in ht:
			ht[B[i]] = 0
		if B[i - 1] != B[i + 1]:
			ht[B[i]] += 1
		else:
			ht[B[i]] += 2
	if K == 1:
		print(0)
	else:
		print(' '.join([str(len(B) - 3 - ht[k + 1]) for k in range(K)]))


t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 1:
		print(0)
		continue
	elif k == 2:
		print('0 0')
		continue
	brr = [arr[0]]
	count = 0
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			brr.append(arr[i])
			count += 1
	temp = {}
	if n > 1:
		if brr[0] != brr[1]:
			temp[brr[0]] = 1
	for i in range(1, len(brr) - 1):
		if brr[i - 1] != brr[i + 1]:
			if brr[i] not in temp.keys():
				temp[brr[i]] = 1
			else:
				temp[brr[i]] += 1
		elif brr[i] not in temp.keys():
			temp[brr[i]] = 2
		else:
			temp[brr[i]] += 2
	m = len(brr)
	if brr[m - 1] != brr[m - 2]:
		if brr[m - 1] not in temp.keys():
			temp[brr[m - 1]] = 1
		else:
			temp[brr[m - 1]] += 1
	result = []
	for i in range(k):
		result.append(count - temp[i + 1])
	print(*result)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ugly = [0] * k
	prev = -1
	same = 0
	for i in range(n - 1):
		if prev != -1 and prev != a[i + 1] and (a[i + 1] != a[i]) and (prev != a[i]):
			ugly[a[i] - 1] -= 1
		if a[i] != a[i + 1]:
			ugly[a[i] - 1] += 1
			ugly[a[i + 1] - 1] += 1
			prev = a[i]
		elif a[i] == a[i + 1]:
			same += 1
	ugly = [n - i - 1 - same for i in ugly]
	print(*ugly)


from collections import defaultdict
for _ in range(int(input())):
	(n, t) = map(int, input().split())
	a = list(map(int, input().split()))
	f = defaultdict(list)
	for i in range(t):
		f[i + 1] = [0, 0]
	l = -1
	c = 0
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			if l == a[i + 1]:
				f[a[i]][1] += 1
			else:
				f[a[i]][0] += 1
			l = a[i]
			c += 1
	if c >= 1:
		f[a[n - 1]][0] += 1
	for i in range(t):
		print(c - (f[i + 1][0] + f[i + 1][1] * 2), end=' ')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	prev = -1
	now = -1
	nxt = -1
	ans = 0
	key = [0] * k
	for i in range(n - 1):
		ind = n - i - 1
		now = arr[ind]
		nxt = arr[ind - 1]
		if prev != -1 and prev != nxt and (nxt != now) and (prev != now):
			key[now - 1] -= 1
		if now != nxt:
			key[now - 1] += 1
			key[nxt - 1] += 1
			prev = now
		elif now == nxt:
			ans += 1
	for i in key:
		print(n - i - 1 - ans, end=' ')
	print('\n')


import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	prev = l[0]
	ind = 0
	d = {}
	for i in range(n):
		if l[i] == prev:
			continue
		else:
			p = [ind, i - 1]
			if prev in d:
				d[prev].append(p)
			else:
				d[prev] = [p]
			prev = l[i]
			ind = i
	p = [ind, n - 1]
	if prev in d:
		d[prev].append(p)
	else:
		d[prev] = [p]
	prev = l[n - 1]
	ind = n - 1
	ugli = 0
	for i in range(1, n):
		if l[i] != l[i - 1]:
			ugli += 1
	ans = []
	for i in range(1, k + 1):
		u = ugli
		for j in d[i]:
			x = j[0]
			y = j[1]
			if x == 0 or y == n - 1:
				u = u - 1
			elif l[x - 1] == l[y + 1]:
				u = u - 2
			else:
				u = u - 1
		ans.append(u)
	if k == 1:
		print(0)
	else:
		print(*ans)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	p = []
	q = []
	p.append(arr[0])
	ugli = 0
	for i in range(1, n):
		if arr[i - 1] != arr[i]:
			p.append(arr[i])
	for i in range(1, len(p)):
		if p[i - 1] != p[i]:
			ugli += 1
	for i in range(k + 1):
		q.append(ugli)
	for i in range(len(p)):
		if i + 1 < len(p):
			q[p[i]] = q[p[i]] - 1
		if i - 1 >= 0:
			q[p[i]] = q[p[i]] - 1
		if i - 1 >= 0 and i + 1 < len(p) and (p[i + 1] != p[i - 1]):
			q[p[i]] = q[p[i]] + 1
	for i in range(1, k + 1):
		print(q[i], end=' ')
	print('')
	t = t - 1


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	cur = 0
	for i in range(1, n):
		if a[i] != a[i - 1]:
			cur += 1
	x = [0] * (k + 1)
	last = -1
	for i in range(n):
		if i > 0 and a[i] != a[i - 1]:
			x[a[i]] += 1
			if a[i] == last or last == -1:
				x[a[i - 1]] += 1
			last = a[i - 1]
	x = x[1:]
	for i in range(k):
		x[i] = cur - x[i]
	print(*x)


t = int(input())
while t:
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	Prev = -1
	Now = -1
	Next = -1
	same = 0
	key = [0] * k
	for i in range(n - 1):
		ind = n - i - n - 1
		Now = arr[ind]
		Next = arr[ind - 1]
		if Prev != -1 and Prev != Next and (Next != Now) and (Prev != Now):
			key[Now - 1] -= 1
		if Now != Next:
			key[Now - 1] += 1
			key[Next - 1] += 1
			Prev = Now
		elif Now == Next:
			same += 1
	for i in key:
		print(n - i - 1 - same, end=' ')
	print()
	t -= 1


t = int(input())
while t:
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A1 = [A[0]]
	total = 0
	for i in range(N - 1):
		if A[i] == A[i + 1]:
			continue
		else:
			A1.append(A[i + 1])
			total += 1
	d = {}
	for i in range(1, len(A1) - 1):
		if A1[i - 1] != A1[i + 1]:
			if A1[i] in d.keys():
				d[A1[i]] += 1
			else:
				d[A1[i]] = 1
		elif A1[i] in d.keys():
			d[A1[i]] += 2
		else:
			d[A1[i]] = 2
	if A1[0] in d.keys():
		d[A1[0]] += 1
	else:
		d[A1[0]] = 1
	if A1[-1] in d.keys():
		d[A1[-1]] += 1
	else:
		d[A1[-1]] = 1
	if len(A1) == 1:
		print(0)
	else:
		for i in range(1, K + 1):
			print(total - d[i], end=' ')
	print('\n')
	t -= 1


def ugly(s):
	res = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			res += 1
	return res
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	mapp = dict()
	stk = [s[0]]
	mapp[s[0]] = 1
	for i in range(1, n):
		if stk[-1] != s[i]:
			stk.append(s[i])
			if s[i] in mapp:
				mapp[s[i]] += 1
			else:
				mapp[s[i]] = 1
	l = len(stk) - 1
	totalUgly = l
	if k > 100:
		for i in range(1, l):
			if stk[i - 1] == stk[i + 1]:
				mapp[stk[i]] += 1
		for i in range(1, k + 1):
			print(totalUgly - mapp[i], end=' ')
	else:
		for i in range(1, k + 1):
			temp = [j for j in stk if j != i]
			try:
				while True:
					temp.remove(i)
			except:
				pass
			print(ugly(temp), end=' ')
	print()
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	i = 0
	while i < n and l[i] == l[0]:
		i += 1
	d = {}
	c = 0
	for j in range(1, n):
		if l[j] != l[j - 1]:
			c += 1
	if i < n:
		d[l[i - 1]] = -1
	while i < n:
		y = l[i - 1]
		x = l[i]
		while i < n and l[i] == x:
			i += 1
		r = 0
		if i < n and l[i] == y:
			r = 2
		else:
			r = 1
		if x in d:
			d[x] -= r
		else:
			d[x] = -r
	for j in range(1, k + 1):
		if j in d:
			print(c + d[j], end=' ')
		else:
			print(c, end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 1:
		print(0)
		continue
	brr = [0]
	c = [arr[0]]
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			c.append(arr[i])
	x = len(c)
	ugle = x - 1
	for i in range(1, x - 1):
		if c[i - 1] == c[i + 1]:
			brr.append(1)
		else:
			brr.append(-1)
	dic = {}
	for i in range(x):
		if c[i] in dic.keys():
			dic[c[i]].append(i)
		else:
			dic[c[i]] = [i]
	ans = [0 for i in range(k)]
	for i in range(1, k + 1):
		u = ugle
		for j in dic[i]:
			if j == 0 or j == x - 1:
				u -= 1
			elif brr[j] == 1:
				u -= 2
			else:
				u -= 1
		ans[i - 1] = u
	for i in range(k):
		print(ans[i], end=' ')
	print()


from bisect import *
from collections import *
from sys import stdin, stdout
from queue import *
from itertools import *
from heapq import *
from random import *
from statistics import *
from math import *
from re import *
import array
import operator
from copy import *
lines = stdin.readlines()
out = stdout.write
lines.reverse()

def input():
	return lines.pop().strip('\n')

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

def readStrList():
	return list(map(str, input().split()))

def binary_search(arr, value, l, h):
	k = bisect_left(arr, value, l, h)
	if k != h and arr[k] == value:
		return True
	return False
for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	vis = []
	ans = defaultdict(int)
	i = 0
	for (i, j) in groupby(arr):
		vis.append(i)
	for i in range(len(vis)):
		if i == 0:
			ans[vis[0]] += 1
		elif i == len(vis) - 1:
			ans[vis[len(vis) - 1]] += 1
		elif vis[i - 1] == vis[i + 1]:
			ans[vis[i]] += 2
		else:
			ans[vis[i]] += 1
	cnt = len(vis) - 1
	if k == 1:
		print('0')
		continue
	for i in range(k):
		print(cnt - ans[i + 1], end=' ')
	print()


for t in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	st = []
	newlis = []
	for i in range(n - 1):
		if lis[i] != lis[i + 1]:
			newlis.append(lis[i])
	newlis.append(lis[-1])
	nnew = len(newlis)
	res = [nnew - 1] * (k + 1)
	if nnew == 1:
		print(0)
	else:
		for i in range(nnew - 2):
			if newlis[i] == newlis[i + 2]:
				res[newlis[i + 1]] -= 2
			else:
				res[newlis[i + 1]] -= 1
		res[newlis[0]] -= 1
		res[newlis[-1]] -= 1
		print(*res[1:])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.append('#')
	ans = []
	for i in range(n):
		if arr[i] != arr[i + 1]:
			ans.append(arr[i])
	n = len(ans)
	check = [0] * (k + 2)
	for i in range(1, n):
		if i == 1:
			(p1, p2) = (min(ans[i], ans[i - 1]), max(ans[i], ans[i - 1]))
			if p1 + 1 == p2:
				check[0] += 1
				check[p1] -= 1
				check[p2 + 1] += 1
			else:
				check[0] += 1
				check[p1] -= 1
				check[p1 + 1] += 1
				check[p2] -= 1
				check[p2 + 1] += 1
		elif ans[i] == ans[i - 2]:
			(p1, p2) = (min(ans[i], ans[i - 1]), max(ans[i], ans[i - 1]))
			if p1 + 1 == p2:
				check[0] += 1
				check[p1] -= 1
				check[p2 + 1] += 1
			else:
				check[0] += 1
				check[p1] -= 1
				check[p1 + 1] += 1
				check[p2] -= 1
				check[p2 + 1] += 1
		else:
			p1 = ans[i]
			check[0] += 1
			check[p1] -= 1
			check[p1 + 1] += 1
	for i in range(1, k + 2):
		check[i] += check[i - 1]
	print(*check[1:k + 1])


t = int(input())
while t:
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	prev = -1
	now = -1
	same = 0
	key = [0] * k
	for i in range(n - 1):
		ind = n - i - 1
		now = arr[ind]
		next = arr[ind - 1]
		if prev != -1 and prev != next and (next != now) and (prev != now):
			key[now - 1] -= 1
		if now != next:
			key[now - 1] += 1
			key[next - 1] += 1
			prev = now
		elif now == next:
			same += 1
	for i in key:
		print(n - 1 - i - same, end=' ')
	print()
	t -= 1


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [a[0]]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			continue
		else:
			b.append(a[i])
	us = len(b) - 1
	ct = defaultdict(int)
	for b_i in b:
		ct[b_i] += 1
	usr = defaultdict(int)
	for i in range(len(b)):
		if i + 1 < len(b) and i - 1 >= 0 and (b[i - 1] == b[i + 1]):
			usr[b[i]] += 2
		else:
			usr[b[i]] += 1
	if k == 1:
		print(0)
	else:
		print(' '.join((str(us - usr[i]) for i in range(1, k + 1))))


def funcx(n, k, l1):
	if k == 1:
		print(0)
		return
	if k == 2:
		print(0, 0)
		return
	if k == n:
		for i in range(n):
			print(k - 2, end=' ')
		print()
		return
	else:
		d1 = {}
		d2 = {}
		ld = -1
		i = 1
		t = 0
		while i < n:
			if l1[i] != l1[i - 1]:
				d1[l1[i]] = d1.get(l1[i], 0) + 1
				d1[l1[i - 1]] = d1.get(l1[i - 1], 0) + 1
				t += 1
				if l1[i] != ld and ld != -1:
					d2[l1[i - 1]] = d2.get(l1[i - 1], 0) + 1
				ld = l1[i - 1]
			i += 1
		arr = [t for i in range(k)]
		for i in d1:
			arr[i - 1] -= d1[i]
		for i in d2:
			arr[i - 1] += d2[i]
		print(*arr)
		return
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l1 = [int(i) for i in input().split()]
	funcx(n, k, l1)


from collections import Counter

def solve():
	(size, K) = map(int, input().split())
	array = list(map(int, input().split()))
	dict = {}
	k1 = Counter(array)
	for i in range(size):
		try:
			if dict[array[i]][-1][1] == i - 1:
				dict[array[i]][-1][1] = i
			else:
				dict[array[i]].append([i, i])
		except:
			dict[array[i]] = [[i, i]]
	match = [0 for i in range(K + 1)]
	total = 0
	for i in range(1, size):
		if array[i] == array[i - 1]:
			total += 1
			match[array[i - 1]] += 1
	output = []
	for i in range(1, K + 1):
		ans = total - match[i]
		if size - k1[i] == 0:
			output.append(0)
		else:
			for j in range(len(dict[i])):
				if dict[i][j][0] > 0 and dict[i][j][1] < size - 1:
					if array[dict[i][j][0] - 1] == array[dict[i][j][1] + 1]:
						ans += 1
			output.append(size - k1[i] - 1 - ans)
	return output
remained_test_cases = 1
remained_test_cases = int(input())
while remained_test_cases > 0:
	print(*solve())
	remained_test_cases -= 1


import sys
input = sys.stdin.readline
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip('\r\n')

def solve():
	(n, k) = rl()
	a = rl()
	ans = [0] * k
	t = l = r = 0
	for i in range(n):
		if a[i] == a[r]:
			r = i
			continue
		t += 1
		ans[a[i] - 1] += 1
		ans[a[r] - 1] += 1
		if l > 0 and l < n - 1 and (a[l - 1] != a[r + 1]):
			ans[a[r] - 1] -= 1
		l = r = i
	for i in range(k):
		ans[i] = t - ans[i]
	return ans
for _ in range(ri()):
	print(*solve())


t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = list((int(i) for i in input().split()))
	if n < 1000:
		for j in range(1, k + 1):
			new = []
			for l in a:
				if l != j:
					new.append(l)
			ugliness = 0
			if len(new) == 0:
				print(ugliness, end=' ')
				continue
			last = new[0]
			for l in new:
				if l != last:
					last = l
					ugliness += 1
			print(ugliness, end=' ')
		print()
		continue
	ugl_sum = list([0 for i in range(k)])
	if len(a) >= 2:
		if a[0] != a[1]:
			ugl_sum[a[0] - 1] += 1
		if a[-1] != a[-2]:
			ugl_sum[a[-1] - 1] += 1
	else:
		print(0)
		continue
	for j in range(1, n - 1):
		if a[j] != a[j - 1]:
			ugl_sum[a[j] - 1] += 1
		index = j
		while a[index] == a[index - 1]:
			if index == 1:
				break
			index -= 1
		else:
			if a[index - 1] == a[j + 1]:
				ugl_sum[a[j] - 1] += 1
	ugliness = 0
	for j in range(n - 1):
		if a[j] != a[j - 1]:
			ugliness += 1
	for j in ugl_sum:
		print(ugliness - j, end=' ')
	print()


t = int(input())
for i in range(t):
	d = {}
	c = {}
	fin = []
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	f = []
	s = 0
	f.append(l[0])
	for j in range(len(l)):
		if l[j] != f[-1]:
			f.append(l[j])
	for j in f:
		if j not in d.keys():
			d[j] = 1
		else:
			d[j] += 1
	for j in range(1, b + 1):
		c[j] = 0
	for j in range(2, len(f)):
		if f[j] == f[j - 2]:
			c[f[j - 1]] += 1
	for j in d.keys():
		s += d[j]
	for j in range(1, b + 1):
		pr1 = s - d[j]
		pr1 -= c[j]
		if pr1 != 0:
			fin.append(pr1 - 1)
		else:
			fin.append(pr1)
	print(*fin)


t = int(input())
while t != 0:
	t = t - 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 1:
		print('0')
	else:
		a1 = list()
		d = dict()
		d1 = dict()
		for i in range(n):
			if i == 0:
				a1.append(a[i])
				d[a[i]] = 1
			elif a[i - 1] != a[i]:
				a1.append(a[i])
				if d.get(a[i]):
					d[a[i]] += 1
				else:
					d[a[i]] = 1
		for i in range(len(a1) - 2):
			if a1[i] == a1[i + 2]:
				if d1.get(a1[i + 1]):
					d1[a1[i + 1]] -= 1
				else:
					d1[a1[i + 1]] = -1
		for i in range(1, k + 1):
			kok = 0
			if d1.get(i):
				kok = d1[i]
			print(kok + len(a1) - d[i] - 1, end=' ')
		print()


def main():
	t = int(input())
	for i in range(t):
		temp = list(map(int, input().split()))
		(n, k) = (temp[0], temp[1])
		a = list(map(int, input().split()))
		if k == 1:
			print(0)
			continue
		umax = 0
		a2 = [a[0]]
		for j in range(1, len(a)):
			if a[j] != a[j - 1]:
				a2.append(a[j])
				umax += 1
		dictt = {}
		for j in range(k):
			dictt[j + 1] = umax
		dictt[a2[0]] -= 1
		dictt[a2[-1]] -= 1
		for j in range(1, len(a2) - 1):
			if a2[j - 1] == a2[j + 1]:
				dictt[a2[j]] -= 2
			else:
				dictt[a2[j]] -= 1
		ans = []
		for j in sorted(dictt.keys()):
			ans.append(str(dictt[j]))
		print(' '.join(ans))
main()


for tc in range(int(input())):
	ls = list(map(int, input().split()))
	lk = list(map(int, input().split()))
	dis = dict()
	newlk = []
	for x in lk:
		if len(newlk) == 0:
			newlk.append(x)
		elif newlk[-1] != x:
			newlk.append(x)
	if len(newlk) == 1:
		print(0)
		continue
	ct = 0
	dis[newlk[0]] = 1
	for x in range(1, len(newlk) - 1):
		if newlk[x] != newlk[x - 1]:
			ct += 1
			if dis.get(newlk[x]) is None:
				dis[newlk[x]] = 1
			else:
				dis[newlk[x]] += 1
		if newlk[x + 1] != newlk[x]:
			if newlk[x + 1] == newlk[x - 1]:
				if dis.get(newlk[x]) is None:
					dis[newlk[x]] = 1
				else:
					dis[newlk[x]] += 1
	if newlk[-1] != newlk[-2]:
		ct += 1
		if dis.get(newlk[-1]) is None:
			dis[newlk[-1]] = 1
		else:
			dis[newlk[-1]] += 1
	res = []
	for x in range(1, ls[1] + 1):
		res.append(ct - dis[x])
	print(*res)


test = int(input())
for t in range(test):
	(n, k) = map(int, input().split())
	ls = [int(i) for i in input().split()]
	ans = [0 * i for i in range(k)]
	tc = 0
	last = ls[0]
	if k == 1:
		print(0)
		continue
	for i in range(1, n):
		c = ls[i]
		p = ls[i - 1]
		if c == p:
			continue
		else:
			tc += 1
			if last == c:
				ans[p - 1] += 2
			else:
				ans[p - 1] += 1
			last = p
	ans2 = [tc for i in range(k)]
	ans[ls[n - 1] - 1] += 1
	a = [x1 - x2 for (x1, x2) in zip(ans2, ans)]
	print(*a)


import sys

def build_arr(arr):
	new = []
	last = -1
	for x in arr:
		if x != last:
			last = x
			new.append(last)
	return new
for _ in range(int(input().strip())):
	(n, k) = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	arr = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	if k == 1:
		print(0)
		continue
	if k == 2:
		print('0 0')
		continue
	arr = build_arr(arr)
	curr = len(arr) - 1
	n = len(arr)
	eat = dict()
	for i in range(1, k + 1):
		eat[i] = 0
	for i in range(n):
		if i == 0 or i == n - 1:
			eat[arr[i]] += 1
		elif arr[i - 1] == arr[i + 1]:
			eat[arr[i]] += 2
		else:
			eat[arr[i]] += 1
	ans = [0] * k
	for i in range(1, k + 1):
		ans[i - 1] = curr - eat[i]
	print(*ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, k) = mp()
	l = li()
	d = defaultdict(int)
	pre = [0] * n
	suff = [0] * n
	first_ind = defaultdict(lambda x: -1)
	last_ind = defaultdict(lambda x: -1)
	last_ind[l[0]] = 0
	for i in range(1, n):
		pre[i] = pre[i - 1]
		last_ind[l[i]] = i
		if l[i] != l[i - 1]:
			pre[i] += 1
	first_ind[l[-1]] = n - 1
	for i in range(n - 2, -1, -1):
		first_ind[l[i]] = i
		suff[i] = suff[i + 1]
		if l[i] != l[i + 1]:
			suff[i] += 1
	i = 0
	indexes = [-1] * (k + 1)
	while i < n:
		j = i
		if indexes[l[i]] >= 0:
			d[l[i]] += pre[i - 1] - pre[indexes[l[i]] + 1]
		while j < n and l[j] == l[i]:
			j += 1
		if i - 1 >= 0 and j < n and (l[i - 1] != l[j]):
			d[l[i]] += 1
		indexes[l[i]] = j - 1
		i = j
	ANS = []
	for i in range(1, k + 1):
		if first_ind[i] == -1:
			ANS.append(pre[-1])
		else:
			ans = d[i]
			if first_ind[i] != 0:
				ans += pre[first_ind[i] - 1]
			if last_ind[i] != n - 1:
				ans += suff[last_ind[i] + 1]
			ANS.append(ans)
	print(*ANS)
for _ in range(inp()):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s = s.split()
	a = [int(s[0])]
	check = []
	for _ in range(k + 1):
		check.append([])
	check[int(s[0])].append(0)
	for i in s:
		if int(i) != a[-1]:
			a.append(int(i))
			check[int(i)].append(len(a) - 1)
	total = len(a) - 1
	if total > 0:
		for i in range(1, k + 1):
			if len(check[i]) > 0:
				ans = total
				for j in check[i]:
					if i == a[j]:
						if j > 0 and j < total:
							if a[j - 1] == a[j + 1]:
								ans -= 2
							elif a[j - 1] != a[j + 1]:
								ans -= 1
						elif j == 0:
							ans -= 1
						elif j == total:
							ans -= 1
				print(ans, end=' ')
		print()
	else:
		print(0)


def rajeev(a):
	b = [a[0]]
	for r in range(1, len(a)):
		if b[-1] == a[r]:
			continue
		else:
			b.append(a[r])
	return b
t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = rajeev(a)
	yy = len(c)
	ss = []
	for rr in range(k + 1):
		ss.append(0)
	for y in range(1, yy - 1):
		if c[y - 1] == c[y + 1]:
			ss[c[y]] += 2
		else:
			ss[c[y]] += 1
	ss[c[0]] += 1
	ss[c[-1]] += 1
	ans = []
	for g in range(1, k + 1):
		if yy - ss[g] - 1 >= 0:
			ans.append(str(yy - ss[g] - 1))
		else:
			ans.append(str(0))
	print(' '.join(ans))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().rstrip().split()))
	res = 0
	for i in range(1, n):
		if A[i] != A[i - 1]:
			res += 1
	B = list()
	x = -1
	for i in range(n):
		if A[i] != x:
			B.append(A[i])
		x = A[i]
	res1 = [res] * (k + 1)
	l = len(B)
	for i in range(l):
		if i == 0 or i == l - 1:
			res1[B[i]] -= 1
		elif B[i - 1] == B[i + 1]:
			res1[B[i]] -= 2
		else:
			res1[B[i]] -= 1
	if k <= 2:
		for i in range(k):
			print(0, end=' ')
		print()
	else:
		for i in range(1, k + 1):
			print(res1[i], end=' ')
		print()


import sys
from collections import deque
from collections import Counter
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	(size, k) = ari()
	arr = ari()
	reducearr = []
	intial = arr[0]
	reducearr.append(intial)
	for i in range(1, size):
		if intial != arr[i]:
			reducearr.append(arr[i])
			intial = arr[i]
	maxpossible = 0
	n = len(reducearr)
	for i in range(len(reducearr) - 1):
		if reducearr[i] != reducearr[i + 1]:
			maxpossible += 1
	total = [maxpossible] * (n + 1)
	for i in range(n):
		if i + 1 < n and i - 1 >= 0:
			total[reducearr[i]] -= 2
		elif i - 1 >= 0 or i + 1 < n:
			total[reducearr[i]] -= 1
		if i - 1 >= 0 and i + 1 < n and (reducearr[i + 1] != reducearr[i - 1]):
			total[reducearr[i]] += 1
	print(*total[1:k + 1])
	return

	def doit(ele):
		newarr = []
		for i in reducearr:
			if i != ele:
				newarr.append(i)
		count = 0
		for i in range(len(newarr) - 1):
			if newarr[i] != newarr[i + 1]:
				count += 1
		return count
	result = []
	for i in range(1, n + 1):
		result.append(doit(i))
	print(*result)
	return
for _ in range(test_case):
	ans()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(j) for j in input().split()]
	b = []
	mapp = [0 for j in range(10 ** 5 + 3)]
	j = 0
	while j < n:
		ele = a[j]
		b.append(a[j])
		while j + 1 < n and a[j + 1] == ele:
			j += 1
		j += 1
	if len(b) == 1:
		print(0)
		continue
	for j in b:
		mapp[j] += 1
	ans = [len(b) - 1 for j in range(k)]
	for j in range(2, len(b)):
		if b[j] == b[j - 2]:
			ans[b[j - 1] - 1] -= 1
	for j in range(len(ans)):
		ans[j] -= mapp[j + 1]
		print(ans[j], end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	d = dict()
	start = 0
	end = 0
	last = ar[0]
	for i in range(1, n):
		if ar[i] == last:
			end += 1
		elif last in d:
			d[last].append([start, end])
			start = i
			end = i
			last = ar[i]
		else:
			d[last] = [[start, end]]
			start = i
			end = i
			last = ar[i]
	if last in d:
		d[last].append([start, end])
	else:
		d[last] = [[start, end]]
	count = 0
	for i in range(1, n):
		if ar[i] != ar[i - 1]:
			count += 1
	ans = [0] * k
	for i in range(1, k + 1):
		c = count
		for val in d[i]:
			if val[0] - 1 >= 0:
				if ar[val[0]] != ar[val[0] - 1]:
					c -= 1
			if val[1] + 1 < n:
				if ar[val[1]] != ar[val[1] + 1]:
					c -= 1
			if val[0] - 1 >= 0 and val[1] + 1 < n:
				if ar[val[0] - 1] != ar[val[1] + 1]:
					c += 1
		ans[i - 1] = c
	print(*ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	tc = 0
	for i in range(1, n):
		if a[i] != a[i - 1]:
			tc += 1
	if n == 1:
		print(0)
	else:
		d = dict()
		kd = dict()
		nli = []
		for i in range(1, n):
			if a[i] != a[i - 1]:
				nli.append(a[i - 1])
		nli.append(a[-1])
		n = len(nli)
		for i in range(k):
			d[i + 1] = 0
		for i in range(1, n):
			if nli[i] != nli[i - 1]:
				d[nli[i]] += 1
				d[nli[i - 1]] += 1
				if i != n - 1:
					if nli[i - 1] != nli[i + 1] and nli[i] != nli[i + 1]:
						if nli[i] in kd:
							kd[nli[i]] += 1
						else:
							kd[nli[i]] = 1
		ans = []
		for i in range(k):
			if i + 1 in kd:
				ans.append(tc + kd[i + 1] - d[i + 1])
			else:
				ans.append(tc - d[i + 1])
		print(*ans)


try:
	from collections import defaultdict
	for _ in range(int(input())):
		(n, k) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		a1 = []
		if k == 1:
			print(0)
		else:
			d = {}
			d = defaultdict(lambda : 0, d)
			d1 = {}
			d1 = defaultdict(lambda : 0, d1)
			i = 0
			while i < n:
				b = a[i]
				while i < n and a[i] == b:
					i += 1
				d[b] += 1
				a1.append(b)
			l = len(a1)
			for i in range(1, l - 1):
				if a1[i - 1] == a1[i + 1]:
					d1[a1[i]] += 1
			s = 0
			for i in range(1, k + 1):
				s += d[i]
			for i in range(1, k + 1):
				print(s - d[i] - d1[i] - 1, end=' ')
			print()
except:
	pass


def myfunc(n, k, arr):
	ug = 0
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			ug += 1
	m = [True] * n
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			m[i] = False
	aux = []
	for i in range(n):
		if m[i]:
			aux.append(arr[i])
	a = [[] for _ in range(k + 1)]
	for i in range(len(aux)):
		a[aux[i]].append(i)
	ans = []
	for i in range(1, k + 1):
		t = 0
		for idx in a[i]:
			if aux[max(idx - 1, 0)] == aux[min(idx + 1, len(aux) - 1)]:
				t += 2
			else:
				t += 1
		ans.append(ug - t)
	if k == 1:
		ans = [0]
	print(*ans)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	myfunc(n, k, arr)


def func():
	(n, k) = map(int, input().split())
	v = list(map(int, input().split()))
	ug = 0
	l = [v[0]]
	for i in range(1, n):
		if l[-1] != v[i]:
			l.append(v[i])
	n = len(l)
	for i in range(n - 1):
		if l[i] != l[i + 1]:
			ug += 1
	ans = [ug for i in range(k + 1)]
	for i in range(n):
		if i + 1 < n:
			ans[l[i]] -= 1
		if i - 1 >= 0:
			ans[l[i]] -= 1
		if i - 1 >= 0 and i + 1 < n and (l[i + 1] != l[i - 1]):
			ans[l[i]] += 1
	for i in range(1, k + 1):
		print(ans[i], end=' ')
	print()
t = int(input())
for i in range(t):
	func()


from collections import defaultdict
from sys import stdin, stdout, setrecursionlimit
(readline, writeline) = (stdin.readline, stdout.write)
setrecursionlimit(100005)
for _ in range(int(readline())):
	(n, k) = map(int, readline().split())
	arr = list(map(int, readline().split()))
	lst = [arr[0]]
	for i in range(1, n):
		if arr[i] != lst[-1]:
			lst.append(arr[i])
	n = len(lst)
	ans = [n - 1] * (k + 1)
	for i in range(n):
		if i + 1 < n:
			ans[lst[i]] -= 1
		if i - 1 >= 0:
			ans[lst[i]] -= 1
		if i + 1 < n and i - 1 >= 0 and (lst[i - 1] != lst[i + 1]):
			ans[lst[i]] += 1
	print(*ans[1:])


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 1:
		print(0)
		continue
	h = {arr[0]: 0}
	total = 0
	pre = 0
	cur = arr[0]
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			continue
		if arr[i] == pre:
			if arr[i - 1] in h:
				h[arr[i - 1]] += 2
			else:
				h[arr[i - 1]] = 2
			pre = arr[i - 1]
			total += 1
		else:
			if arr[i - 1] in h:
				h[arr[i - 1]] += 1
			else:
				h[arr[i - 1]] = 1
			pre = arr[i - 1]
			total += 1
	if arr[-1] in h:
		h[arr[-1]] += 1
	else:
		h[arr[-1]] = 1
	for i in range(1, k + 1):
		print(total - h[i], end=' ')
	print()


def input_int():
	return int(input())

def input_multiple():
	return map(int, input().split())
t = input_int()
while t > 0:
	(n, k) = input_multiple()
	a = list(input_multiple())
	b = []
	last = ''
	for i in a:
		if i != last:
			b.append(i)
		last = i
	ka = [0] * k
	lb = len(b)
	for i in range(1, lb - 1):
		if b[i - 1] == b[i + 1]:
			ka[b[i] - 1] += 1
		ka[b[i] - 1] += 1
	ka[b[0] - 1] += 1
	ka[b[-1] - 1] += 1
	for i in range(k):
		if lb - ka[i] - 1 < 0:
			print(0)
		else:
			print(lb - ka[i] - 1, end=' ')
	print()
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	if k == 1:
		print(0)
		continue
	for i in range(1, n):
		if l[i] != l[i - 1]:
			c += 1
	d = {i: 0 for i in range(1, k + 1)}
	prev = {i: i for i in range(1, k + 1)}
	for i in range(n):
		if i - 1 >= 0 and l[i] != l[i - 1]:
			if l[i] == prev[l[i - 1]]:
				d[l[i - 1]] += 2
			else:
				d[l[i - 1]] += 1
		if i - 1 >= 0 and l[i] != l[i - 1]:
			prev[l[i]] = l[i - 1]
	d[l[-1]] += 1
	for i in range(1, k + 1):
		print(c - d[i], end=' ')
	print()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007
for _ in range(stdint()):
	(n, k) = stdmap()
	arr = stdarr()
	split = [arr[0]]
	total = Counter()
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			split.append(arr[i])
	total = len(split) - 1
	c = Counter()
	for i in range(1, len(split) - 1):
		if split[i - 1] == split[i + 1]:
			c[split[i]] += 2
		else:
			c[split[i]] += 1
	c[split[0]] += 1
	c[split[-1]] += 1
	res = []
	for i in range(1, k + 1):
		res.append(max(total - c[i], 0))
	print(*res)


def solve(N, K, arr):
	temp = [arr[0]]
	for i in range(1, N):
		if temp[-1] != arr[i]:
			temp.append(arr[i])
	arr = temp
	N = len(temp)
	total = 0
	for i in range(N - 1):
		if arr[i] != arr[i + 1]:
			total += 1
	ans = [total for _ in range(K + 1)]
	for i in range(N):
		if i + 1 < N:
			ans[arr[i]] -= 1
		if i - 1 >= 0:
			ans[arr[i]] -= 1
		if i - 1 >= 0 and i + 1 < N and (arr[i + 1] != arr[i - 1]):
			ans[arr[i]] += 1
	return ' '.join(map(str, ans[1:]))
t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solve(N, K, arr))


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	d = defaultdict(int)
	l = defaultdict(int)
	ug = 0
	a = [int(i) for i in input().split()]
	for i in range(1, n):
		if a[i] != a[i - 1]:
			ug += 1
			l[a[i]] = a[i - 1]
			if l[a[i - 1]] == a[i]:
				d[a[i - 1]] += 2
			else:
				d[a[i - 1]] += 1
		if i == n - 1 and l[a[n - 1]] != 0:
			d[a[i]] += 1
	for i in range(1, k + 1):
		print(ug - d[i], end=' ')
	print('')


for hjikdjfsk in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = {}
	b = [a[0]]
	for i in range(1, n):
		if a[i - 1] != a[i]:
			b.append(a[i])
	for i in range(1, len(b) - 1):
		if b[i - 1] == b[i + 1]:
			try:
				d[b[i]] += 2
			except:
				d[b[i]] = 2
		else:
			try:
				d[b[i]] += 1
			except:
				d[b[i]] = 1
	if len(b) >= 2:
		try:
			d[b[0]] += 1
		except:
			d[b[0]] = 1
		try:
			d[b[-1]] += 1
		except:
			d[b[-1]] = 1
	else:
		print(0)
		continue
	u = 0
	for i in range(1, n):
		if a[i - 1] != a[i]:
			u += 1
	for i in range(1, k + 1):
		print(u - d[i], end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	if k == 1:
		print('0')
		continue
	blk = [A[0]]
	for i in range(1, n):
		if A[i - 1] != A[i]:
			blk.append(A[i])
	(dit1, dit2) = ({}, {})
	for i in range(1, k + 1):
		(dit1[i], dit2[i]) = (0, 0)
	for i in blk:
		dit1[i] += 1
	for i in range(1, len(blk) - 1):
		if blk[i - 1] == blk[i + 1]:
			dit2[blk[i]] += 1
	blocks = len(blk) - 1
	for i in range(1, k + 1):
		print(blocks - dit1[i] - dit2[i], end=' ')
	print()


T = int(input())
import collections
for _ in range(T):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	stack = []
	for i in range(n):
		if len(stack) == 0:
			stack.append(ar[i])
		elif stack[-1] == ar[i]:
			continue
		else:
			stack.append(ar[i])
	tot = len(stack) - 1
	d = collections.defaultdict(int)
	for i in range(len(stack)):
		d[stack[i]] = d[stack[i]] + 1
		if i != len(stack) - 1 and i != 0:
			if stack[i + 1] == stack[i - 1]:
				d[stack[i]] = d[stack[i]] + 1
	ans = [0 for i in range(k)]
	for i in range(1, k + 1):
		ans[i - 1] = tot - d[i]
	if len(stack) == 1:
		print(0)
		continue
	for i in range(len(ans)):
		if i != len(ans) - 1:
			print(ans[i], end=' ')
		else:
			print(ans[i])


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	MAP = defaultdict(list)
	for i in range(k):
		MAP[i + 1] = [0, 0]
	last = -1
	count = 0
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			if last == arr[i + 1]:
				MAP[arr[i]][1] += 1
			else:
				MAP[arr[i]][0] += 1
			last = arr[i]
			count += 1
	if count >= 1:
		MAP[arr[n - 1]][0] += 1
	for i in range(k):
		print(count - (MAP[i + 1][0] + MAP[i + 1][1] * 2), end=' ')
	print()


from sys import stdin
t = int(stdin.readline().rstrip())
while t > 0:
	(n, k) = map(int, stdin.readline().strip().split(' '))
	test = list(map(int, stdin.readline().strip().split(' ')))
	arr = []
	for i in range(len(test)):
		if i == 0:
			arr.append(test[i])
		elif test[i] != arr[-1]:
			arr.append(test[i])
	n = len(arr)
	totaluglines = 0
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			totaluglines += 1
	new_arr = [totaluglines] * (k + 1)
	for i in range(n):
		if i + 1 < n:
			new_arr[arr[i]] -= 1
		if i - 1 >= 0:
			new_arr[arr[i]] -= 1
		if i - 1 >= 0 and i + 1 < n and (arr[i + 1] != arr[i - 1]):
			new_arr[arr[i]] += 1
	for i in range(1, k + 1):
		print(new_arr[i], end=' ')
	print()
	t -= 1


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	prev = None
	ans = []
	for ch in arr:
		if prev == None or ch != prev:
			ans.append(ch)
		prev = ch
	res = [max(len(ans) - 1, 1)] * k
	d = defaultdict(int)
	for i in range(len(ans)):
		if i > 0 and i < len(ans) - 1 and (ans[i - 1] == ans[i + 1]):
			d[ans[i]] += 2
		else:
			d[ans[i]] += 1
	for i in range(k):
		res[i] -= d[i + 1]
	print(*res)


import sys
input = sys.stdin.readline
from collections import defaultdict
num_test_cases = int(input())
for _ in range(num_test_cases):
	(length, num_unique_digits) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	reduced_arr = [arr[0]]
	for x in arr[1:]:
		if x != reduced_arr[-1]:
			reduced_arr += [x]
	base_ugliness = len(reduced_arr) - 1
	discount = defaultdict(int)
	discount[reduced_arr[0]] = 1
	for i in range(1, len(reduced_arr) - 1):
		x = reduced_arr[i]
		if reduced_arr[i - 1] == reduced_arr[i + 1]:
			discount[x] += 2
		else:
			discount[x] += 1
	if len(reduced_arr) > 1:
		discount[reduced_arr[-1]] += 1
	ans = [max(base_ugliness - discount[x], 0) for x in range(1, num_unique_digits + 1)]
	print(*ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		arr = [int(input())]
	else:
		arr = list(map(int, input().split()))
	i = 0
	curr = arr[i]
	fin = [curr]
	total_ugliness = 0
	while i < n:
		if curr != arr[i]:
			total_ugliness += 1
			curr = arr[i]
			fin.append(curr)
		i += 1
	if curr != arr[i - 1]:
		total_ugliness += 1
		curr = arr[i - 1]
		fin.append(curr)
	pos = [None] * (k + 1)
	for i in range(len(fin)):
		if not pos[fin[i]]:
			pos[fin[i]] = [i]
		else:
			pos[fin[i]].append(i)
	op = []
	for i in range(1, k + 1):
		temp = 0
		for j in pos[i]:
			if j - 1 > -1 and j + 1 < len(fin):
				if fin[j - 1] == fin[j + 1]:
					temp += 1
		op.append(max(0, total_ugliness - temp - len(pos[i])))
	print(*op)


from sys import *
input = stdin.readline
for u in range(int(input())):
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().split()))
	v = []
	for i in range(n):
		if i == 0:
			v.append(a[i])
		elif a[i] != v[-1]:
			v.append(a[i])
	m = len(v)
	t = 0
	for i in range(m - 1):
		if v[i] != v[i + 1]:
			t += 1
	ans = [t for i in range(k + 1)]
	for i in range(m):
		if i + 1 < m:
			ans[v[i]] -= 1
		if i - 1 >= 0:
			ans[v[i]] -= 1
		if i - 1 >= 0 and i + 1 < m and (v[i + 1] != v[i - 1]):
			ans[v[i]] += 1
	print(*ans[1:])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	if k == 1 or n == 1:
		print(0)
		continue
	for i in range(1, n):
		if arr[i - 1] != arr[i]:
			count += 1
	ans = [count] * k
	ans[arr[0] - 1] -= 1
	p = arr[0]
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			if p == arr[i + 1]:
				ans[arr[i] - 1] -= 1
			p = arr[i]
			ans[arr[i + 1] - 1] -= 1
	for i in range(k - 1):
		print(ans[i], end=' ')
	print(ans[k - 1])


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	if k == 2:
		print('0 0')
		continue
	dic = {}
	for i in range(1, k + 1):
		dic[i] = 0
	ans = 0
	t = [li[0]]
	for i in range(1, n):
		if t[-1] != li[i]:
			t.append(li[i])
	for i in range(n - 1):
		if li[i] != li[i + 1]:
			dic[li[i]] += 1
			dic[li[i + 1]] += 1
	li = t.copy()
	dic2 = {}
	for i in range(1, k + 1):
		dic2[i] = 0
	for i in range(0, len(li) - 2):
		if li[i] != li[i + 1]:
			if li[i] != li[i + 2]:
				dic2[li[i + 1]] += 1
	ans = len(t)
	for i in range(1, k + 1):
		print(ans - dic[i] - 1 + dic2[i], end=' ')
	print()