You are given an integer N where N ≤ 10. Consider any array A with length N where each element can either be 0, 1, or 2, we define f(A) as the number of extrema in A. You need to find the sum of f(A) over all possible arrays A.

Note:
In an array A, we consider A_{i} as an extremum if it is strictly greater than both of its neighbors (i.e. A_{i} > A_{i - 1} and A_{i} > A_{i + 1}), or if it is strictly smaller than both of its neighbors (i.e. A_{i} < A_{i - 1} and A_{i} < A_{i + 1}). Note that first and last elements are not counted as extremum.
Extrema is the plural of extremum.

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

- The first line of the input contains an integer T - the number of test cases. The test cases then follow.
- The only line of each test case contains one integer N.

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

For each test case, output on a single the sum of f(A) over all possible arrays A.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10$

----- Sample Input 1 ------ 
3
1
3
5
----- Sample Output 1 ------ 
0
10
270

----- explanation 1 ------ 
- Test case $1$:
- $A = [0]$. Then $f(A) = 0$.
- $A = [1]$. Then $f(A) = 0$.
- $A = [2]$. Then $f(A) = 0$.

Therefore the answer is $0$.
- Test case $2$: There are $10$ arrays $A$ with $f(A) = 1$:
- $A = [0, 1, 0]$.
- $A = [0, 2, 0]$.
- $A = [0, 2, 1]$.
- $A = [1, 2, 0]$.
- $A = [1, 2, 1]$.
- $A = [2, 1, 2]$.
- $A = [2, 0, 2]$.
- $A = [2, 0, 1]$.
- $A = [1, 0, 2]$.
- $A = [1, 0, 1]$. 

The remaining $A$'s has $f(A) = 0$. Therefore the answer is $1 \cdot 10 = 10$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	s = 0
	if n == 3:
		print(10)
	elif n > 3:
		print(pow(3, n - 3) * 10 * (n - 2))
	else:
		print(0)


def funk(n):
	if n == 1:
		return [[0], [1], [2]]
	p = funk(n - 1)
	ans = []
	for r in p:
		ans += [r + [0]]
		ans += [r + [1]]
		ans += [r + [2]]
	return ans

def ffunk(a, n):
	an = 0
	if n < 3:
		return 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1] or (a[i] < a[i - 1] and a[i] < a[i + 1]):
			an += 1
	return an
t = int(input())
for tt in range(t):
	n = int(input())
	a = funk(n)
	ans = 0
	for r in a:
		ans += ffunk(r, n)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1 or n == 2:
		print(0)
	elif n == 3:
		print(10)
	else:
		print(3 ** (n - 3) * 10 * (n - 2))


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(0)
	else:
		print(3 ** (n - 3) * 10 * (n - 2))


for _ in range(int(input())):
	N = int(input())
	if N == 2 or N == 1:
		print(0)
		continue
	print(3 ** (N - 3) * 10 * (N - 2))


a = int(input())
for i in range(a):
	n = int(input())
	s = 0
	if n == 3:
		print(10)
	elif n > 3:
		s = pow(3, n - 3) * 8 * (n - 2)
		s += s // 4
		print(s)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(0)
	else:
		a = 3 ** (n - 3)
		b = n - 2
		ans = 10 * b * a
		print(ans)


read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]

def solve():
	n = read_int()
	if n < 3:
		print(0)
		return
	ans = 10 * (n - 2) * 3 ** (n - 3)
	print(ans)
for _ in range(int(input())):
	solve()


read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]

def count_ext(seq):
	count = 0
	for i in range(1, len(seq) - 1):
		if seq[i] > seq[i - 1] and seq[i] > seq[i + 1] or (seq[i] < seq[i - 1] and seq[i] < seq[i + 1]):
			count += 1
	return count

def solve():
	n = read_int()
	if n < 3:
		print(0)
		return
	seq = [0] * n
	ans = 0
	while len(seq) > 0:
		ans += count_ext(seq)
		while len(seq) > 0 and seq[-1] == 2:
			seq.pop()
		if len(seq) > 0:
			seq[-1] += 1
			while len(seq) < n:
				seq.append(0)
	print(ans)
for _ in range(int(input())):
	solve()


def solve(lst):
	if len(lst) == n:
		ans = 0
		for i in range(1, n - 1):
			if lst[i - 1] > lst[i] < lst[i + 1] or lst[i - 1] < lst[i] > lst[i + 1]:
				ans += 1
		return ans
	ans = 0
	for i in range(3):
		lst.append(i)
		ans += solve(lst)
		lst.pop()
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve([]))


def solve(lst, length):
	if length == n:
		ans = 0
		for i in range(1, n - 1):
			if lst[i - 1] > lst[i] < lst[i + 1] or lst[i - 1] < lst[i] > lst[i + 1]:
				ans += 1
		return ans
	ans = 0
	for i in range(3):
		ans += solve(lst + [i], length + 1)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve([], 0))


from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from cmath import pi
from distutils import extension
import sys
import math
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7

def count(ans, n, st=''):
	if len(st) == n:
		for l in range(1, n - 1):
			if int(st[l - 1]) < int(st[l]) > int(st[l + 1]) or int(st[l - 1]) > int(st[l]) < int(st[l + 1]):
				ans[0] += 1
		return
	for k in ['0', '1', '2']:
		count(ans, n, st + k)
for l in range(ii()):
	n = ii()
	if n <= 2:
		print(0)
		continue
	ans = [0]
	count(ans, n)
	print(ans[0])


T = int(input())
for i in range(T):
	N = int(input())
	res = []

	def rec(selected, ind):
		if ind == N:
			res.append(selected.copy())
			return
		for i in (0, 1, 2):
			selected.append(i)
			rec(selected, ind + 1)
			selected.pop()
		return
	rec([], 0)
	ans = 0
	for r in res:
		for j in range(1, N - 1):
			if r[j - 1] < r[j] and r[j] > r[j + 1] or (r[j - 1] > r[j] and r[j] < r[j + 1]):
				ans += 1
	print(ans)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		n = nl()
		print(max(0, (n - 2) * 10 * 3 ** (n - 3)))
main()


n = int(input())
for i in range(n):
	a = int(input())
	if a >= 3:
		print(10 * (a - 2) * 3 ** (a - 3))
	else:
		print(0)


def n(k):
	if k < 3:
		return 0
	else:
		return 10 * 3 ** (k - 3) * (k - 2)
test_cases = int(input())
while test_cases != 0:
	data = int(input())
	print(n(data))
	test_cases -= 1


def FindNumOfPeaks(ArrayList, ArraySize):
	NumOfPeaks = 0
	for i in range(1, ArraySize - 1):
		if ArrayList[i] > ArrayList[i + 1] and ArrayList[i] > ArrayList[i - 1] or (ArrayList[i] < ArrayList[i + 1] and ArrayList[i] < ArrayList[i - 1]):
			NumOfPeaks = NumOfPeaks + 1
	return NumOfPeaks
TotalTestCases = int(input())
for i in range(TotalTestCases):
	ArraySize = int(input())
	TotalPeaks = 0
	if ArraySize > 2:
		ArrayList = [0] * ArraySize
		for i in range(ArraySize):
			ArrayList[i] = 0
		for i in range(pow(3, ArraySize)):
			TotalPeaks = TotalPeaks + FindNumOfPeaks(ArrayList, ArraySize)
			ArrayList[0] = ArrayList[0] + 1
			if ArrayList[0] == 3:
				for i in range(ArraySize - 1):
					if ArrayList[i] == 3:
						ArrayList[i] = 0
						ArrayList[i + 1] = ArrayList[i + 1] + 1
	print(TotalPeaks)


try:
	for _ in range(int(input())):
		n = int(input())
		if n < 3:
			print(0)
		else:
			print(10 * (n - 2) * 3 ** (n - 3))
except:
	pass


t = int(input())
arr = []
for i in range(t):
	arr.append(int(input()))
n = 0
for i in range(t):
	n = arr[i]
	if n < 3:
		print(0)
	else:
		print(10 * (n - 2) * 3 ** (n - 3))


for T in range(int(input())):
	N = int(input())
	sum = 0
	if N == 3:
		print(10)
	elif N > 3:
		sum = pow(3, N - 3) * 8 * (N - 2)
		sum += sum // 4
		print(sum)
	else:
		print(0)


t = int(input())
for i in range(0, t):
	k = int(input())
	if k < 3:
		print(0)
	else:
		k2 = int(10 * (k - 2) * 3 ** (k - 3))
		print(k2)


t = int(input())
for _ in range(t):
	n = int(input())
	c = 0
	if n > 2:
		c = 10 * (n - 2) * 3 ** (n - 3)
	print(c)


for _ in range(int(input())):
	x = int(input())
	if x > 2:
		temp = 3 ** (x - 3)
		print(10 * (x - 2) * temp)
	else:
		print(0)


x = int(input())
for l in range(0, x):
	k = int(input())
	h = 3 ** (k - 3)
	if k > 2:
		print(10 * (k - 2) * h)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	count = 0
	if n == 3:
		print('10')
	elif n > 3:
		count = pow(3, n - 3) * 8 * (n - 2)
		count += count // 4
		print(count)
	else:
		print('0')


for i in range(int(input())):
	n = int(input())
	sum_e = 0
	if n > 2:
		sum_e = 10 * (n - 2) * 3 ** (n - 3)
	print(sum_e)


def calA(n):
	if n <= 3:
		return 0
	n -= 3
	return 10 * 3 ** n

def func(n):
	if n < 3:
		return 0
	if n == 3:
		return 10
	return func(n - 1) * 3 + calA(n)
t = int(input())
a = []
while t:
	t -= 1
	a.append(int(input()))
for i in a:
	print(func(i))


n = int(input())
for i in range(n):
	n1 = int(input())
	res = 10 * (n1 - 2) * 3 ** (n1 - 3)
	if n1 < 3:
		print('0')
	else:
		print(res)


for i in range(int(input())):
	num = int(input())
	if num < 3:
		print('0')
	else:
		print(10 * (num - 2) * pow(3, num - 3))


for k in range(int(input())):
	a = int(input())
	if a <= 2:
		print(0)
	else:
		print(10 * 3 ** (a - 3) * (a - 2))


from sys import stdin
a = [0, 0, 10, 60, 270, 1080, 4050, 14580, 51030, 174960]
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	print(a[n - 1])


from multiprocessing.connection import answer_challenge
for _ in range(int(input())):
	n = int(input())
	if n >= 3:
		ans = (n - 2) * 10 * 3 ** (n - 3)
		print(ans)
	else:
		print(0)


t = int(input())
for c in range(t):
	n = int(input())
	if n < 3:
		print(0)
	else:
		print(10 * pow(3, n - 3) * (n - 2))


for _ in range(int(input())):
	N = int(input())
	print(10 * (N - 2) * pow(3, N - 3) if N > 2 else 0)


t = int(input())

def solve(x):

	def peak(ar):
		cnt = 0
		for i in range(1, len(ar) - 1):
			(a, b, c) = (ar[i - 1], ar[i], ar[i + 1])
			if b > a and b > c or (b < a and b < c):
				cnt += 1
		return cnt

	def lsts(tmp, n, ans):
		if len(tmp) == n:
			ans.append(tmp)
			return
		for i in range(3):
			lsts(tmp + [i], n, ans)
	out = []
	lsts([], x, out)
	ans = 0
	for i in out:
		ans += peak(i)
	return ans
for i in range(t):
	y = int(input())
	print(solve(y))


for T in range(int(input())):
	N = int(input())
	if N < 3:
		print(0)
	else:
		print(10 * (N - 2) * 3 ** (N - 3))


t = int(input())
for i in range(t):
	n = int(input())
	r = 0
	if n > 2:
		r = 10 * ((n - 2) * 3 ** (n - 3))
	print(int(r))


def sum():
	global s
	for j in range(1, n - 1):
		if l[j] > l[j + 1] and l[j] > l[j - 1] or (l[j] < l[j + 1] and l[j] < l[j - 1]):
			s += 1

def iterate(x, y):
	for i in range(3):
		l[x] = i
		if y == 1:
			sum()
		else:
			iterate(x + 1, y - 1)
for _ in range(int(input())):
	global s
	s = 0
	l = [-1]
	n = int(input())
	l = l * n
	iterate(0, n)
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	if n < 3:
		print(0)
	else:
		a = n - 2
		print(10 * a * 3 ** (a - 1))


def backtracking(arr, latest: int, diff: int, summ: int, n: int):
	if len(arr) == 1:
		return sum([backtracking(arr + [x], x, x - latest, summ, n) for x in range(0, 3)])
	if len(arr) >= n:
		return summ
	nextsum = 0
	for i in range(0, 3):
		if diff * (latest - i) > 0:
			nextsum += backtracking(arr + [i], i, i - latest, summ + 1, n)
		else:
			nextsum += backtracking(arr + [i], i, i - latest, summ, n)
	return nextsum

def solve():
	t = int(input())
	for _ in range(0, t):
		n = int(input())
		print(sum([backtracking([x], x, 0, 0, n) for x in range(0, 3)]))
solve()


test = int(input())
for _ in range(test):
	n = int(input())
	if n <= 2:
		print(0)
	else:
		ans = 10 * (n - 2) * pow(3, n - 3)
		print(ans)


N = int(input())
arr = []
for i in range(N):
	arr.append(int(input()))
for item in arr:
	if item < 3:
		print(0)
	else:
		val = 10 * (item - 2) * 3 ** (item - 3)
		print(val)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1 or n == 2:
		print(0)
	else:
		arr = [0 for i in range(n)]
		sum = 0
		for i in range(3 ** n):
			temp = i
			for j in range(n):
				arr[j] = temp % 3
				temp = int(temp / 3)
			cnt = 0
			for j in range(1, n - 1):
				if arr[j] > arr[j - 1] and arr[j] > arr[j + 1] or (arr[j] < arr[j - 1] and arr[j] < arr[j + 1]):
					cnt += 1
			sum += cnt
		print(sum)


import sys

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

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def subHelper(arr):
	n = len(arr)
	ans = 0
	for i in range(1, n - 1, 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1] or (arr[i] < arr[i - 1] and arr[i] < arr[i + 1]):
			ans += 1
	return ans

def helper(arr, num, ans):
	if num == 0:
		ans[0] += subHelper(arr)
		return
	elif num > 0:
		arr.append(0)
		helper(arr, num - 1, ans)
		arr.pop()
		arr.append(1)
		helper(arr, num - 1, ans)
		arr.pop()
		arr.append(2)
		helper(arr, num - 1, ans)
		arr.pop()

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = []
		ans = [0]
		helper(arr, n, ans)
		get_print_int(ans[0])
solve()