Read problems statements in Mandarin Chinese and Russian as well. 

Mike is a famous traveler. He visits about 100 countries a year and buys the flag of each country he has been to.

Mike knows, that there are some flags, that correspond to one pattern, but colored in different ways. E.g. the flag of Ireland(link) and the flag of Belgium(link). In this problem we consider only five 2,2cm✕1,1cm patterns of flags:

There are N different colors available to paint the flags and the colors are denoted by integers from 1 to N.

Mike wants you to count the number of different well-painted flags. We call a flag well-painted if it's made according to the following algorithm:

Pick up one of the flag patterns considered above;
Paint each one-colored polygon on the pattern in a color encoded by an integer from 1 to N. Different colors are encoded with different integers. If two different one-colored polygons share a common side(not corner), than they must be painted in different colors. In any other case they can be painted in both equal and different colors.

Two flags are different, if they look different(have at least one pixel painted with different color).

Help Mike!

Text version of the pictures:  
Picture 1

112233

112233

112233

111111

222222

333333

112222

112222

113333

122223

111333

144443

111222

333222

333444

Picture 2

112211

112211

112211

221122

221122

221122

111111

222222

111111

222222

111111

222222

------ Input ------ 

The first line of the input contains integer T, denoting the number of testcases. The description of T testcases follows.
The only line of each test case contains integer N, denoting the number of different colors, that can be used while painting a flag pattern.
 
------ Output ------ 

For each testcase, output a single line containing an integer - the answer for the corresponding query.
 
------ Constraints ------ 

1 ≤ T ≤ 10 000;
1 ≤ N ≤ 10 000 for each testcase.
 
----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
0
4
42
----- explanation 1 ------ 

There are four different well-painted flags for N = 2 different colors :

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	print(n * (n - 1) * (n - 1) * 2 + n * (n - 1) * (n - 2) + 2 * (n * (n - 1) * (n - 2) + n * (n - 1) * (n - 2) * (n - 3)))


def combination(n, r):
	if r > n:
		c = 0
	elif r == 2:
		c = n * (n - 1) // 2
	elif r == 3:
		c = n * (n - 1) * (n - 2) // 6
	elif r == 4:
		c = n * (n - 1) * (n - 2) * (n - 3) // 24
	return c
t = input()
for C in range(0, int(t)):
	n = int(input())
	ans = combination(n, 3) * 6 * 5 + combination(n, 2) * 2 * 2 + combination(n, 4) * 24 * 2
	print(ans)


for i in range(int(input())):
	n = int(input())
	ans = 0
	ans += n * (n - 1) * (n - 1)
	ans += n * (n - 1) * (n - 1)
	ans += n * (n - 1) * (n - 2)
	ans += n * (n - 1) * (n - 2) * (n - 2)
	ans += n * (n - 1) * (n - 2) * (n - 2)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	ans += n * (n - 1) * (n - 1)
	ans += n * (n - 1) * (n - 1)
	ans += n * (n - 1) * (n - 2)
	ans += n * (n - 1) * (n - 2) * (n - 2)
	ans += n * (n - 1) * (n - 2) * (n - 2)
	print(ans)


tst = int(input())
for i in range(tst):
	num = int(input())
	ans = 0
	if num == 1:
		ans = 0
	elif num == 2:
		ans = 4
	elif num == 3:
		ans = 42
	else:
		ans = num * (num - 1) * (num - 1) * 2 + num * (num - 1) * (num - 2) + num * (num - 1) * (num - 2) * (num - 2) * 2
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2:
		print(4)
	elif n == 3:
		print(42)
	else:
		print(2 * n * (n - 1) + 5 * n * (n - 1) * (n - 2) + 2 * n * (n - 1) * (n - 2) * (n - 3))


def nCr(n, r):
	if n < r:
		return 0
	(num, den) = (1, 1)
	for i in range(r):
		num *= n - i
		den *= i + 1
	return num // den
for _ in range(int(input())):
	n = int(input())
	print(4 * nCr(n, 2) + 30 * nCr(n, 3) + 48 * nCr(n, 4))


for i in range(int(input())):
	num = int(input())
	ans = 0
	if num >= 2:
		add = 2 * (num * (num - 1))
		ans += add
	if num >= 3:
		add = 5 * num * (num - 1) * (num - 2)
		ans += add
	if num >= 4:
		add = 2 * num * (num - 1) * (num - 2) * (num - 3)
		ans += add
	print(ans)


for _ in range(int(input())):
	N = int(input())
	print(N * (N - 1) * (2 * N * N - 5 * N + 4))


for x in range(int(input())):
	n = int(input())
	if n < 2:
		print(0)
	elif n == 2:
		print(4)
	else:
		p1 = n * (n - 1) + n * (n - 1) * (n - 2)
		p2 = p1
		p3 = n * (n - 1) * (n - 2)
		p4 = n * (n - 1) * (n - 2) + n * (n - 1) * (n - 2) * (n - 3)
		p5 = p4
		print(p1 + p2 + p3 + p4 + p5)


for x in range(int(input())):
	n = int(input())
	a = 0
	a += n * (n - 1) * (n - 1)
	a += n * (n - 1) * (n - 1)
	a += n * (n - 1) * (n - 2)
	a += n * (n - 1) * (n - 2) * (n - 2)
	a += n * (n - 1) * (n - 2) * (n - 2)
	print(a)


import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
for x in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2:
		print(4)
	elif n == 3:
		print(42)
	else:
		print((ncr(n, 3) * 6 + ncr(n, 2) * 2) * 2 + ncr(n, 3) * 6 + (ncr(n, 4) * 24 + ncr(n, 3) * 6) * 2)


T = int(input())
for i in range(0, T):
	a = int(input())
	if a == 1:
		print(0)
	elif a == 2:
		print(4)
	else:
		tyab = 2 * (a * (a - 1) * (a - 2) + a * (a - 1))
		tyc = a * (a - 1) * (a - 2)
		tyde = 2 * (a * (a - 1) * (a - 2) + a * (a - 1) * (a - 2) * (a - 3))
		print(tyab + tyc + tyde)


t = int(input())
for _ in range(t):
	n = int(input())
	flag1 = n * (n - 1) * (n - 1)
	flag2 = n * (n - 1) * (n - 1)
	flag3 = n * (n - 1) * (n - 2)
	flag4 = n * (n - 1) * (n - 2) * (n - 2)
	flag5 = n * (n - 1) * (n - 2) * (n - 2)
	print(flag1 + flag2 + flag3 + flag4 + flag5)


T = int(input())
for _ in range(T):
	N = int(input())
	way1 = N * (N - 1) * (N - 1)
	way2 = N * (N - 1) * (N - 1)
	way3 = N * (N - 1) * (N - 2)
	way4 = N * (N - 1) * (N - 2) * (N - 2)
	way5 = N * (N - 1) * (N - 2) * (N - 2)
	ans = way1 + way2 + way3 + way4 + way5
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = 0
	if n == 1:
		s = 0
	elif n == 2:
		s = 4
	else:
		s = n * (n - 1) * (n - 1) * 2 + n * (n - 1) * (n - 2) + n * (n - 2) * (n - 2) * (n - 1) * 2
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	print(n * (n - 1) * (4 - 5 * n + 2 * n ** 2))


t = int(input())
for _ in range(t):
	n = int(input())
	res = 0
	if n == 1:
		res = 0
	elif n == 2:
		res = 4
	else:
		res = n * (n - 1) * (n - 1) * 2 + n * (n - 1) * (n - 2) + n * (n - 2) * (n - 2) * (n - 1) * 2
	print(res)


import sys
import math
for _ in range(int(input())):
	n = int(input())
	print(n * (n - 1) ** 2 + n * (n - 1) ** 2 + n * (n - 1) * (n - 2) + n * (n - 1) * (n - 2) * (n - 2) + n * (n - 1) * (n - 2) * (n - 2))


import sys
import math

def main(n):
	ans = n * (n - 1) ** 2 + n * (n - 1) ** 2 + n * (n - 1) * (n - 2) + n * (n - 1) * (n - 2) * (n - 2) + n * (n - 1) * (n - 2) * (n - 2)
	return ans
for _ in range(int(input())):
	print(main(int(input())))


T = int(input())
for _ in range(T):
	N = int(input())
	Total = 0
	if N - 1 > 0:
		Total += 2 * (N * (N - 1) * (N - 1))
	if N - 2 > 0:
		Total += N * (N - 1) * (N - 2) + 2 * (N * (N - 1) * (N - 2) * (N - 2))
	print(Total)


for _ in range(int(input())):
	n = int(input())
	t_1 = 2 * n * (n - 1)
	t_2 = 5 * n * (n - 1) * (n - 2)
	t_3 = 2 * n * (n - 1) * (n - 2) * (n - 3)
	print(t_1 + t_2 + t_3)


T = int(input())
for i in range(T):
	N = int(input())
	print(N * (N - 1) * ((N - 1) * 2 + (N - 2) + (N - 2) * (N - 2) * 2))


test = int(input())
for _ in range(test):
	n = int(input())
	print(n * (n - 1) * ((n - 1) * 2 + (n - 2) + (n - 2) * (n - 2) * 2))


for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(0)
	elif N == 2:
		print(4)
	else:
		print(N * (N - 1) * (N - 1) * 2 + N * (N - 1) * (N - 2) + N * (N - 1) * (N - 2) * (N - 2) + N * (N - 1) * (N - 2) * (N - 2))


for i in range(int(input())):
	n = int(input())
	print(n * (n - 1) * ((n - 1) * 2 + (n - 2) + (n - 2) * (n - 2) * 2))


def nC2(n):
	return n * (n - 1)

def nC3(n):
	return n * (n - 1) * (n - 2)

def nC4(n):
	return n * (n - 1) * (n - 2) * (n - 3)
for _ in range(int(input())):
	n = int(input())
	ans = 0
	if n >= 2:
		ans += nC2(n) * 2
	if n >= 3:
		ans += nC3(n) * 5
	if n >= 4:
		ans += nC4(n) * 2
	print(ans)


def nC2(n):
	return n * (n - 1)

def nC3(n):
	return n * (n - 1) * (n - 2)

def nC4(n):
	return n * (n - 1) * (n - 2) * (n - 3)
for _ in range(int(input())):
	n = int(input())
	ans = nC2(n) + nC3(n)
	ans += nC2(n) + nC3(n)
	ans += nC3(n)
	ans += nC3(n) + nC4(n)
	ans += nC4(n) + nC3(n)
	print(ans)


t = int(input())
for z in range(t):
	n = int(input())
	if n == 1:
		print('0')
		continue
	if n == 2:
		print('4')
		continue
	dic = {}
	dic[1] = n
	for i in range(2, 4 + 1):
		dic[i] = dic[i - 1] * (n - i + 1)
	s = 2 * dic[2] + 5 * dic[3] + 2 * dic[4]
	print(s)


for _ in range(int(input())):
	n = int(input())
	ans = 2 * n * (n - 1) + 5 * n * (n - 1) * (n - 2) + 2 * n * (n - 1) * (n - 2) * (n - 3)
	print(ans)


t = int(input())
while t:
	n = int(input())
	ans = 2 * n * (n - 1) * (n - 1) + n * (n - 1) * (n - 2) + 2 * n * (n - 1) * (n - 2) * (n - 2)
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2:
		print(4)
	else:
		count = n * (n - 1) * (n - 1) * 2
		count += n * (n - 1) * (n - 2)
		count += n * (n - 1) * (n - 2) * (n - 2) * 2
		print(count)


t = int(input())
for val in range(0, t):
	n = int(input())
	if n < 2:
		print(0)
	elif n == 2:
		print(4)
	elif n == 3:
		ans = n * (n - 1) * (n - 1) * 2 + n * (n - 1) * (n - 2) * 2 + n * (n - 1) * (n - 2) * (n - 2)
		print(ans)
	else:
		ans = n * (n - 1) * (n - 1) * 2 + n * (n - 1) * (n - 2) * 2 + n * (n - 1) * (n - 2) * (n - 2) + n * (n - 1) * (n - 2) * (n - 3)
		print(ans)


dp = []
for i in range(0, 10001):
	a = i * (i - 1)
	b = i * (i - 1) * (i - 2)
	c = i * (i - 1) * (i - 2) * (i - 3)
	dp.append(2 * a + 5 * b + 2 * c)
t = int(input())
for j in range(0, t):
	print(dp[int(input())])


for t in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n == 2:
		print(2 * n * (n - 1) * (n - 1))
	else:
		x = n * (n - 1)
		y = x * (n - 2) * (2 * n - 3)
		x *= 2 * (n - 1)
		print(x + y)


T = int(input())

def ans(n, p):
	if p == 1:
		if n == 1:
			return 0
		elif n == 2:
			return 2
		else:
			return n * (n - 1) * (n - 1)
	elif p == 3:
		if n <= 2:
			return 0
		else:
			return n * (n - 1) * (n - 2)
	elif p == 4:
		if n <= 2:
			return 0
		elif n == 3:
			return n * (n - 1) * (n - 2)
		else:
			return n * (n - 1) * (n - 2) + n * (n - 1) * (n - 2) * (n - 3)
for i in range(T):
	N = int(input())
	ans12 = ans(N, 1)
	ans3 = ans(N, 3)
	ans45 = ans(N, 4)
	print(2 * ans12 + ans3 + 2 * ans45)


t = int(input())
for i in range(t):
	N = int(input())
	print(2 * N * (N - 1) * (N - 1) + N * (N - 1) * (N - 2) + 2 * N * (N - 1) * (N - 2) * (N - 2))


string = input()
test = int(string)
for m in range(test):
	num = input()
	n = int(num)
	ans = 0
	ans = 2 * n * (n - 1) * (n - 2) * (n - 2) + 2 * n * (n - 1) * (n - 1) + n * (n - 1) * (n - 2)
	print(ans)


from sys import stdin, stdout

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

def listInput():
	return list(map(int, sin().split()))

def printBS(li):
	if not li:
		return
	for i in range(len(li) - 1):
		stdout.write('%d ' % li[i])
	stdout.write('%d\n' % li[-1])

def nCr(n, r):
	if n < r:
		return 0
	num = 1
	den = 1
	for i in range(r):
		num *= n - i
		den *= i + 1
	return num // den
t = int(sin())
for _ in range(t):
	n = int(sin())
	print(4 * nCr(n, 2) + 30 * nCr(n, 3) + 48 * nCr(n, 4))


for i in range(int(input())):
	n = int(input())
	ans = n * (n - 1) * (2 * n ** 2 - 5 * n + 4)
	print(ans)


import sys

def inp():
	return input()

def readInt():
	return int(inp())

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

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

def makeMatrix(x, y, value):
	a = [0] * x
	for i in range(x):
		a[i] = [value] * y
	return a
tc = readInt()
while tc:
	tc -= 1
	n = readInt()
	ans = 0
	if n > 2:
		ans += n * (n - 1) * (n - 2) * 2
	if n > 1:
		ans += n * (n - 1) * 2
	if n > 2:
		ans += n * (n - 1) * (n - 2)
	if n > 3:
		ans += n * (n - 1) * (n - 2) * (n - 3) * 2
	if n > 2:
		ans += n * (n - 1) * (n - 2) * 2
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	ans = 2 * n * (n - 1) + 5 * n * (n - 1) * (n - 2) + 2 * n * (n - 1) * (n - 2) * (n - 3)
	print(ans)


for tc in range(int(input().strip())):
	N = int(input().strip())
	ans = 0
	if N > 1:
		ans = 2 * N * (N - 1) * (N - 1)
	if N > 2:
		ans += N * (N - 1) * (N - 2)
		ans += N * (N - 1) * (N - 2) * (N - 2)
		ans += N * (N - 1) * (N - 2) * (N - 2)
	print(ans)


for t in range(0, int(input())):
	n = int(input())
	print(2 * n * (n - 1) * (n - 1) + n * (n - 1) * (n - 2) + 2 * n * (n - 1) * (n - 2) * (n - 2))


t = int(input())
for z in range(t):
	color = int(input())
	print(color * (color - 1) * (2 * color * color - 5 * color + 4))