Given an $n\times n\times n$ cube, let $f(x,y,z)$ (where $1\leq x,y,z\leq n$) denote the value stored in cell $(x,y,z)$. 

A $k\times k\times k$ sub-cube (where $1\leq k\leq n$) of an $n\times n\times n$ cube is considered to be special if the maximum value stored in any cell in the sub-cube is equal to $\boldsymbol{\mbox{k}}$.

For each $\boldsymbol{\mbox{k}}$ in the inclusive range $[1,n]$, calculate the number of special sub-cubes. Then print each $\textit{count}_k$ as a single line of space-separated integers (i.e., $\textit{count}_1\ \textit{count}_2\ \textbf{.... count}_n$).

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. The $2\cdot q$ subsequent lines describe each query over two lines:

The first line contains an integer, $n$, denoting the side length of the initial cube.
The second line contains $n^{3}$ space-separated integers describing an array of $n^{3}$ integers in the form $a_0,a_1,\ldots,a_{n^3-1}$. The integer in some cell $(x,y,z)$ is calculated using the formula $a[(x-1)\cdot n^2+(y-1)\cdot n+z]$.

Constraints

$1\leq q\leq5$
$1\leq n\leq50$
$1\leq f(x,y,z)\leq n$ where $1\leq x,y,z\leq n$

Output Format

For each query, print $n$ space-separated integers where the $i^{\mbox{th}}$ integer denotes the number of special sub-cubes for $k=i$.

Sample Input
2
2
2 1 1 1 1 1 1 1
2
1 1 1 1 2 1 1 2

Sample Output
7 1
6 1

Explanation

We must perform the following $q=2$ queries:

We have a cube of size $n=2$ and must calculate the number of special sub-cubes for the following values of $\boldsymbol{\mbox{k}}$:

$k=1$: There are $2^3=8$ sub-cubes of size $1$ and seven of them have a maximum value of $1$ written inside them. So, for $k=1$, the answer is $7$. 
$k=2$: There is only one sub-cube of size $2$ and the maximum number written inside it is $2$. So, for $k=2$, the answer is $1$.    

We then print the respective values for each $\boldsymbol{\mbox{k}}$ as a single line of space-separated integers (i.e., 7 1).

We have a cube of size $n=2$ and must calculate the number of special sub-cubes for the following values of $\boldsymbol{\mbox{k}}$:   

$k=1$: There are $2^3=8$ sub-cubes of size $1$ and six of them have a maximum value of $1$ written inside them. So, for $k=1$, the answer is $\boldsymbol{6}$. 
$k=2$: There is only one sub-cube of size $2$ and the maximum number written inside it is $2$. So, for $k=2$, the answer is $1$.        

We then print the respective values for each $\boldsymbol{\mbox{k}}$ as a single line of space-separated integers (i.e., 6 1).

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def is_special(data, x_start, y_start, z_start, k):
	for x in range(x_start, x_start + k):
		for y in range(y_start, y_start + k):
			for z in range(z_start, z_start + k):
				cell = data[x][y][z]
				if cell > k:
					return False
	return True

def count(data, point_partition, n):
	result = []
	for k in range(1, n + 1):
		result.append(str(count_k(data, point_partition[k], point_partition[k + 1:], n, k)))
	return result

def count_k(data, points, higher_point_partition, n, k):
	bound = n - k + 1
	visit_table = [[[False for z in range(bound)] for y in range(bound)] for x in range(bound)]
	counter = 0
	for point in points:
		count_point_k(data, n, point, visit_table, k, True)
	for higher_points in higher_point_partition:
		for higher_point in higher_points:
			count_point_k(data, n, higher_point, visit_table, k, False)
	for x in range(bound):
		for y in range(bound):
			for z in range(bound):
				if visit_table[x][y][z] == True:
					counter += 1
	return counter

def count_point_k(data, n, point, visit_table, k, mark):
	counter = 0
	x_l = max(point[0] - k + 1, 0)
	x_u = min(point[0], n - k) + 1
	y_l = max(point[1] - k + 1, 0)
	y_u = min(point[1], n - k) + 1
	z_l = max(point[2] - k + 1, 0)
	z_u = min(point[2], n - k) + 1
	for x in range(x_l, x_u):
		for y in range(y_l, y_u):
			for z in range(z_l, z_u):
				visit_table[x][y][z] = mark

def reshape_data(data, n):
	result = []
	point_partition = [[] for i in range(n + 1)]
	y_cursor = None
	z_cursor = None
	for x in range(n):
		y_cursor = []
		for y in range(n):
			z_cursor = []
			for z in range(n):
				cell_value = data[n * n * x + n * y + z]
				z_cursor.append(cell_value)
				point_partition[cell_value].append((x, y, z))
			y_cursor.append(z_cursor)
		result.append(y_cursor)
	return (result, point_partition)
q = int(input())
for i in range(q):
	n = int(input())
	data = [int(x) for x in input().split(' ')]
	(data, point_partition) = reshape_data(data, n)
	print(' '.join(count(data, point_partition, n)))


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def countCubes(cubes, n):
	specialCubeCount = []
	k = 1
	other = [0 for _ in range((n - 1) ** 3)]
	while n > 0:
		count = 0
		for i in range(n ** 3):
			if cubes[i] == k:
				count += 1
		specialCubeCount.append(count)
		for x in range(n - 1):
			xIndex = x * n * n
			newX = x * (n - 1) * (n - 1)
			for y in range(n - 1):
				newY = newX + y * (n - 1)
				yIndex = xIndex + y * n
				for z in range(n - 1):
					index = yIndex + z
					largest = max(cubes[index], cubes[index + 1], cubes[index + n], cubes[index + n + 1], cubes[index + n * n], cubes[index + n * n + 1], cubes[index + n * n + n], cubes[index + n * n + n + 1])
					other[newY + z] = largest
		(other, cubes) = (cubes, other)
		n -= 1
		k += 1
	return specialCubeCount
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	results = countCubes(a, n)
	print(' '.join(map(str, results)))


def recursiveCubeCount(cubes, n, k, results):
	if len(cubes) == 0:
		return results
	count = 0
	for cube in cubes:
		if cube == k:
			count += 1
	results.append(count)
	newCubes = [0 for _ in range((n - 1) ** 3)]
	for x in range(n - 1):
		xIndex = x * n * n
		newX = x * (n - 1) * (n - 1)
		for y in range(n - 1):
			newY = newX + y * (n - 1)
			yIndex = xIndex + y * n
			for z in range(n - 1):
				index = yIndex + z
				largest = max(cubes[index], cubes[index + 1], cubes[index + n], cubes[index + n + 1], cubes[index + n * n], cubes[index + n * n + 1], cubes[index + n * n + n], cubes[index + n * n + n + 1])
				newCubes[newY + z] = largest
	recursiveCubeCount(newCubes, n - 1, k + 1, results)
	return results

def countCubes(cubes, n):
	specialCubeCount = []
	k = 1
	other = [0 for _ in range((n - 1) ** 3)]
	while n > 0:
		count = 0
		for i in range(n ** 3):
			if cubes[i] == k:
				count += 1
		specialCubeCount.append(count)
		for x in range(n - 1):
			xIndex = x * n * n
			newX = x * (n - 1) * (n - 1)
			for y in range(n - 1):
				newY = newX + y * (n - 1)
				yIndex = xIndex + y * n
				for z in range(n - 1):
					index = yIndex + z
					largest = max(cubes[index], cubes[index + 1], cubes[index + n], cubes[index + n + 1], cubes[index + n * n], cubes[index + n * n + 1], cubes[index + n * n + n], cubes[index + n * n + n + 1])
					other[newY + z] = largest
		(other, cubes) = (cubes, other)
		n -= 1
		k += 1
	return specialCubeCount
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	results = countCubes(a, n)
	print(' '.join(map(str, results)))


q = int(input())
for Q in range(q):
	n = int(input())
	a = [int(x) for x in input().split()]
	s = 0
	for x in a:
		if x == 1:
			s += 1
	out = [s]
	m = n * n
	for k in range(2, n + 1):
		r = n - k + 1
		s = 0
		for i in range(r + 1):
			for j in range(r + 1):
				b = n * j + m * i
				for h in range(b, b + r):
					if a[h + 1] > a[h]:
						a[h] = a[h + 1]
		for i in range(r + 1):
			for j in range(r):
				b = n * j + m * i
				for h in range(b, b + r):
					if a[h + n] > a[h]:
						a[h] = a[h + n]
		for i in range(r):
			for j in range(r):
				b = n * j + m * i
				for h in range(b, b + r):
					if a[h + m] > a[h]:
						a[h] = a[h + m]
					if a[h] == k:
						s += 1
		out.append(s)
	print(*out)


def is_special(data, x_start, y_start, z_start, k):
	for x in range(x_start, x_start + k):
		for y in range(y_start, y_start + k):
			for z in range(z_start, z_start + k):
				cell = data[x][y][z]
				if cell > k:
					return False
	return True

def count(data, point_partition, n):
	result = []
	for k in range(1, n + 1):
		result.append(str(count_k(data, point_partition[k], point_partition[k + 1:], n, k)))
	return result

def count_k(data, points, higher_point_partition, n, k):
	bound = n - k + 1
	visit_table = [[[False for z in range(bound)] for y in range(bound)] for x in range(bound)]
	counter = 0
	for point in points:
		count_point_k(data, n, point, visit_table, k, True)
	for higher_points in higher_point_partition:
		for higher_point in higher_points:
			count_point_k(data, n, higher_point, visit_table, k, False)
	for x in range(bound):
		for y in range(bound):
			for z in range(bound):
				if visit_table[x][y][z] == True:
					counter += 1
	return counter

def count_point_k(data, n, point, visit_table, k, mark):
	counter = 0
	x_l = max(point[0] - k + 1, 0)
	x_u = min(point[0], n - k) + 1
	y_l = max(point[1] - k + 1, 0)
	y_u = min(point[1], n - k) + 1
	z_l = max(point[2] - k + 1, 0)
	z_u = min(point[2], n - k) + 1
	for x in range(x_l, x_u):
		for y in range(y_l, y_u):
			for z in range(z_l, z_u):
				visit_table[x][y][z] = mark

def reshape_data(data, n):
	result = []
	point_partition = [[] for i in range(n + 1)]
	y_cursor = None
	z_cursor = None
	for x in range(n):
		y_cursor = []
		for y in range(n):
			z_cursor = []
			for z in range(n):
				cell_value = data[n * n * x + n * y + z]
				z_cursor.append(cell_value)
				point_partition[cell_value].append((x, y, z))
			y_cursor.append(z_cursor)
		result.append(y_cursor)
	return (result, point_partition)
q = int(input())
for i in range(q):
	n = int(input())
	data = [int(x) for x in input().split(' ')]
	(data, point_partition) = reshape_data(data, n)
	print(' '.join(count(data, point_partition, n)))


def is_special(data, x_start, y_start, z_start, k):
	for x in range(x_start, x_start + k):
		for y in range(y_start, y_start + k):
			for z in range(z_start, z_start + k):
				cell = data[x][y][z]
				if cell > k:
					return False
	return True

def count(data, point_partition, n):
	result = []
	for k in range(1, n + 1):
		result.append(str(count_k(data, point_partition[k], point_partition[k + 1:], n, k)))
	return result

def count_k(data, points, higher_point_partition, n, k):
	bound = n - k + 1
	visit_table = [[[False for z in range(bound)] for y in range(bound)] for x in range(bound)]
	counter = 0
	for point in points:
		count_point_k(data, n, point, visit_table, k, True)
	for higher_points in higher_point_partition:
		for higher_point in higher_points:
			count_point_k(data, n, higher_point, visit_table, k, False)
	for x in range(bound):
		for y in range(bound):
			for z in range(bound):
				if visit_table[x][y][z] == True:
					counter += 1
	return counter

def count_point_k(data, n, point, visit_table, k, mark):
	counter = 0
	x_l = max(point[0] - k + 1, 0)
	x_u = min(point[0], n - k) + 1
	y_l = max(point[1] - k + 1, 0)
	y_u = min(point[1], n - k) + 1
	z_l = max(point[2] - k + 1, 0)
	z_u = min(point[2], n - k) + 1
	for x in range(x_l, x_u):
		for y in range(y_l, y_u):
			for z in range(z_l, z_u):
				visit_table[x][y][z] = mark

def reshape_data(data, n):
	result = []
	point_partition = [[] for i in range(n + 1)]
	y_cursor = None
	z_cursor = None
	for x in range(n):
		y_cursor = []
		for y in range(n):
			z_cursor = []
			for z in range(n):
				cell_value = data[n * n * x + n * y + z]
				z_cursor.append(cell_value)
				point_partition[cell_value].append((x, y, z))
			y_cursor.append(z_cursor)
		result.append(y_cursor)
	return (result, point_partition)
q = int(input())
for i in range(q):
	n = int(input())
	data = [int(x) for x in input().split(' ')]
	(data, point_partition) = reshape_data(data, n)
	print(' '.join(count(data, point_partition, n)))


def recursiveCubeCount(cubes, n, k, results):
	if len(cubes) == 0:
		return results
	count = 0
	for cube in cubes:
		if cube == k:
			count += 1
	results.append(count)
	newCubes = [0 for _ in range((n - 1) ** 3)]
	for x in range(n - 1):
		xIndex = x * n * n
		newX = x * (n - 1) * (n - 1)
		for y in range(n - 1):
			newY = newX + y * (n - 1)
			yIndex = xIndex + y * n
			for z in range(n - 1):
				index = yIndex + z
				largest = max(cubes[index], cubes[index + 1], cubes[index + n], cubes[index + n + 1], cubes[index + n * n], cubes[index + n * n + 1], cubes[index + n * n + n], cubes[index + n * n + n + 1])
				newCubes[newY + z] = largest
	recursiveCubeCount(newCubes, n - 1, k + 1, results)
	return results

def countCubes(cubes, n):
	specialCubeCount = []
	k = 1
	other = [0 for _ in range((n - 1) ** 3)]
	while n > 0:
		count = 0
		for i in range(n ** 3):
			if cubes[i] == k:
				count += 1
		specialCubeCount.append(count)
		for x in range(n - 1):
			xIndex = x * n * n
			newX = x * (n - 1) * (n - 1)
			for y in range(n - 1):
				newY = newX + y * (n - 1)
				yIndex = xIndex + y * n
				for z in range(n - 1):
					index = yIndex + z
					largest = max(cubes[index], cubes[index + 1], cubes[index + n], cubes[index + n + 1], cubes[index + n * n], cubes[index + n * n + 1], cubes[index + n * n + n], cubes[index + n * n + n + 1])
					other[newY + z] = largest
		(other, cubes) = (cubes, other)
		n -= 1
		k += 1
	return specialCubeCount
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	results = countCubes(a, n)
	print(' '.join(map(str, results)))


def is_special(data, x_start, y_start, z_start, k):
	for x in range(x_start, x_start + k):
		for y in range(y_start, y_start + k):
			for z in range(z_start, z_start + k):
				cell = data[x][y][z]
				if cell > k:
					return False
	return True

def count(data, point_partition, n):
	result = []
	for k in range(1, n + 1):
		result.append(str(count_k(data, point_partition[k], point_partition[k + 1:], n, k)))
	return result

def count_k(data, points, higher_point_partition, n, k):
	bound = n - k + 1
	visit_table = [[[False for z in range(bound)] for y in range(bound)] for x in range(bound)]
	counter = 0
	for point in points:
		count_point_k(data, n, point, visit_table, k, True)
	for higher_points in higher_point_partition:
		for higher_point in higher_points:
			count_point_k(data, n, higher_point, visit_table, k, False)
	for x in range(bound):
		for y in range(bound):
			for z in range(bound):
				if visit_table[x][y][z] == True:
					counter += 1
	return counter

def count_point_k(data, n, point, visit_table, k, mark):
	counter = 0
	x_l = max(point[0] - k + 1, 0)
	x_u = min(point[0], n - k) + 1
	y_l = max(point[1] - k + 1, 0)
	y_u = min(point[1], n - k) + 1
	z_l = max(point[2] - k + 1, 0)
	z_u = min(point[2], n - k) + 1
	for x in range(x_l, x_u):
		for y in range(y_l, y_u):
			for z in range(z_l, z_u):
				visit_table[x][y][z] = mark

def reshape_data(data, n):
	result = []
	point_partition = [[] for i in range(n + 1)]
	y_cursor = None
	z_cursor = None
	for x in range(n):
		y_cursor = []
		for y in range(n):
			z_cursor = []
			for z in range(n):
				cell_value = data[n * n * x + n * y + z]
				z_cursor.append(cell_value)
				point_partition[cell_value].append((x, y, z))
			y_cursor.append(z_cursor)
		result.append(y_cursor)
	return (result, point_partition)
q = int(input())
for i in range(q):
	n = int(input())
	data = [int(x) for x in input().split(' ')]
	(data, point_partition) = reshape_data(data, n)
	print(' '.join(count(data, point_partition, n)))


def countCubes(cubes, n):
	specialCubeCount = []
	k = 1
	other = [0 for _ in range((n - 1) ** 3)]
	while n > 0:
		count = 0
		for i in range(n ** 3):
			if cubes[i] == k:
				count += 1
		specialCubeCount.append(count)
		for x in range(n - 1):
			xIndex = x * n * n
			newX = x * (n - 1) * (n - 1)
			for y in range(n - 1):
				newY = newX + y * (n - 1)
				yIndex = xIndex + y * n
				for z in range(n - 1):
					index = yIndex + z
					largest = max(cubes[index], cubes[index + 1], cubes[index + n], cubes[index + n + 1], cubes[index + n * n], cubes[index + n * n + 1], cubes[index + n * n + n], cubes[index + n * n + n + 1])
					other[newY + z] = largest
		(other, cubes) = (cubes, other)
		n -= 1
		k += 1
	return specialCubeCount
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	results = countCubes(a, n)
	print(' '.join(map(str, results)))


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


import math
import os
import random
import re
import sys

def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, r, indices, n):
	largest = 1
	for i in indices:
		cur = arr[r + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


import math
import os
import random
import re
import sys

def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')


def findMax(arr, s, indices, n):
	largest = 1
	for i in indices:
		cur = arr[s + i]
		if cur > largest:
			largest = cur
		elif cur == n:
			largest = n
			break
	return largest

def findSpecial(arr, k, n):
	temp = arr
	if k > 1:
		temp = []
		m = n - k + 2
		m2 = m * m
		indices = [0, 1, m, m + 1, m2, m2 + 1, m2 + m, m2 + m + 1]
		for i in range(m - 1):
			start = m2 * i
			for j in range(m - 1):
				for z in range(m - 1):
					largest = findMax(arr, start, indices, n)
					temp.append(largest)
					start += 1
				start += 1
	return temp
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for k in range(1, n + 1):
		arr = findSpecial(arr, k, n)
		print(arr.count(k), end=' ')
	print('')