Monocarp has forgotten the password to his mobile phone. The password consists of $4$ digits from $0$ to $9$ (note that it can start with the digit $0$).

Monocarp remembers that his password had exactly two different digits, and each of these digits appeared exactly two times in the password. Monocarp also remembers some digits which were definitely not used in the password.

You have to calculate the number of different sequences of $4$ digits that could be the password for Monocarp's mobile phone (i. e. these sequences should meet all constraints on Monocarp's password).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 200$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 8$) — the number of digits for which Monocarp remembers that they were not used in the password.

The second line contains $n$ different integers $a_1, a_2, \dots a_n$ ($0 \le a_i \le 9$) representing the digits that were not used in the password. Note that the digits $a_1, a_2, \dots, a_n$ are given in ascending order.


-----Output-----

For each testcase, print one integer — the number of different $4$-digit sequences that meet the constraints.


-----Examples-----

Input
2
8
0 1 2 4 5 6 8 9
1
8
Output
6
216


-----Note-----

In the first example, all possible passwords are: "3377", "3737", "3773", "7337", "7373", "7733".

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Combinatorics

Implementation

Complete search


Solutions:
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = [1] * 10
	for num in arr:
		cnt[num] = 0
	k = sum(cnt)
	return k * (k - 1) * 3
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = 10 - n
	print(3 * (x - 1) * x)


import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	x = 3 * (10 - n) * (10 - n - 1)
	print(x)


from sys import stdin, stdout
import sys
sys.setrecursionlimit(100000)

def fxn(n, arr):
	return 3 * (10 - n) * (9 - n)

def main():
	t = int(input())
	while t != 0:
		n = int(input())
		arr = [int(x) for x in input().split()]
		print(fxn(n, arr))
		t -= 1
main()


import math
n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	m = 10 - m
	print(6 * math.comb(m, 2))


n = int(input())
result = []
for i in range(n):
	input()
	l = 10 - len(input().split(' '))
	m = 0
	for j in range(l):
		for k in range(l):
			if j != k:
				m += 3
	result.append(m)
for i in result:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	matrix = [int(num) for num in input().split()]
	print(6 * (10 - n) * (10 - n - 1) // 2)


a = int(input())
b = []
for i in range(a):
	f = int(input())
	c = input().split(' ')
	d = 10 - len(c)
	e = d * (d - 1) * 3
	b.append(e)
for item in b:
	print(item)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a1 = list(map(int, input().split()))
	a = [0] * 10
	kol = 0
	for j in range(n):
		a[a1[j]] = 1
	for q in range(10):
		if a[q] == 0:
			kol += 1
	if kol == 1:
		ans.append(0)
	else:
		w = kol * (kol - 1) + kol * (kol - 1) * 2
		ans.append(w)
print(*ans, sep='\n')


a = int(input())
for i in range(a):
	n = int(input())
	st = input()
	n = 10 - n
	print(3 * n * (n - 1))


t = int(input())
j = []
for c in range(t):
	n = int(input())
	i = list(map(int, input().split()))
	if 1 <= n <= 8 and n == len(i):
		real = 10 - len(i)
		rightreal = real - 1
		to = real * rightreal
		j1 = to * 4 - to
		j.append(j1)
for t in j:
	print(t)


import math
n = int(input())
for k in range(n):
	s = int(input())
	m = list(map(int, input().split()))
	x = 10 - len(m)
	if x == 0 or x == 1:
		print(0)
	else:
		print(int(6 * math.factorial(x) / (math.factorial(2) * math.factorial(x - 2))))


t = int(input())
while t >= 1:
	c = []
	n = int(input())
	d = list(map(int, input().split()))
	s = []
	for i in range(10):
		if not i in d:
			s.append(i)
	k = len(s)
	factorial1 = 1
	factorial2 = 1
	for i in range(1, k + 1):
		factorial1 *= i
	for i in range(1, k - 1):
		factorial2 *= i
	res = factorial1 / (factorial2 * 2) * 6
	print(int(res), ' ')
	t -= 1


t = int(input())
while t:
	t -= 1
	n = 10 - int(input())
	input()
	print(3 * n * (n - 1))


from math import comb
for _ in range(int(input())):
	n = int(input())
	_a = input()
	print(comb(10 - n, 2) * 6)


import math
t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	a = 10 - len(p)
	if a == 0 or a == 1:
		print(0)
	else:
		print(int(6 * math.factorial(a) / (math.factorial(2) * math.factorial(a - 2))))


def giaithua(n):
	if n == 0:
		return 1
	if n == 1:
		return 1
	return n * giaithua(n - 1)

def tohop(k, n):
	up = giaithua(n)
	low = giaithua(k) * giaithua(n - k)
	return up / low
t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	count = 6 * tohop(2, 10 - n)
	print(int(count))
	t -= 1


def factorial(n):
	pr = 1
	for i in range(1, n + 1):
		pr = pr * i
	return pr
t = int(input())
sp = []
for i in range(1, t + 1):
	n = int(input())
	a = input().split()
	count = 0
	for i in range(len(a)):
		a[i] = int(a[i])
	for j in range(10):
		if j not in a:
			count += 1
	g = int(factorial(count) / (factorial(count - 2) * factorial(2)))
	k = int(g * (factorial(4) / (factorial(4 - 2) * factorial(2))))
	sp.append(k)
print(*sp, sep='\n')


import math
for i in range(int(input())):
	col_elem = int(input())
	input()
	print(math.comb(10 - col_elem, 2) * 6)


for n in [*open(0)][1::2]:
	k = 10 - int(n)
	print(k * (k - 1) * 3)


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	a = 9 - n
	b = a / 2 + 0.5
	print(int(a * b * 6))


t = int(input())
for i in range(t):
	len = int(input())
	l = input().split()
	n = 10 - len
	print((n ** 2 - n) // 2 * 6)


tries = int(input(''))
for i in range(tries):
	L = []
	x = int(input(''))
	L = list(map(int, input().split()))
	B = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	test = 0
	for j in B:
		if not j in L:
			test += 1
	print(test * 3 * (test - 1))


n = int(input())
for i in range(n):
	m = int(input())
	test = 0
	l = list(map(int, input().split()))
	a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	for i in a:
		if not i in l:
			test = test + 1
	print(test * 3 * (test - 1))


test_cases = int(input())
result = []
for case in range(test_cases):
	excluded_n = int(input())
	excluded = [int(number) for number in input().split(' ')]
	rest = 10 - excluded_n
	total = sum(range(0, rest))
	print(total * 6)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	print((10 - n) * (10 - n - 1) * 3)


from math import comb
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(comb(10 - n, 2) * 6)


for n in [*open(0)][1::2]:
	k = 10 - int(n)
	print(k * (k - 1) // 2 * 6)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = 10 - n
	print(int(3 * math.factorial(a) / math.factorial(a - 2)))


t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	print(3 * (10 - len(L)) * (10 - len(L) - 1))


t = int(input())
i = 1
while i <= t:
	a = int(input())
	b = input()
	if a == 0:
		print(45 * 6)
		i += 1
	elif a == 1:
		print(36 * 6)
		i += 1
	elif a == 2:
		print(28 * 6)
		i += 1
	elif a == 3:
		print(21 * 6)
		i += 1
	elif a == 4:
		print(15 * 6)
		i += 1
	elif a == 5:
		print(10 * 6)
		i += 1
	elif a == 6:
		print(6 * 6)
		i += 1
	elif a == 7:
		print(3 * 6)
		i += 1
	elif a == 8:
		print(6)
		i += 1


try:
	test = int(input())
	while test > 0:
		n = int(input())
		inputList = [int(x) for x in input().split()]
		rem = 10 - n - 1
		ans = 6 * (rem * (rem + 1)) / 2
		print(int(ans))
		test -= 1
except EOFError as e:
	print(e)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(ii) for ii in input().split()]
	print((10 - n) * (9 - n) * 3)


testCases = int(input())
for testCase in range(testCases):
	n = int(input())
	listDigits = input().split(' ')
	print((10 - n) * (9 - n) * 3, end='\n')


import math
num_tests = int(input())
for test in range(num_tests):
	num_dig_omitted = int(input())
	dig_omitted = [int(x) for x in input().split(' ')]
	print(math.comb(10 - num_dig_omitted, 2) * 6)


n = int(input())
for testcase in range(0, n):
	digits_remember = int(input())
	digits = input()
	selection = (10 - digits_remember) * (9 - digits_remember) / 2
	total_permutes = int(selection * 6)
	print(total_permutes)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	m = 10 - n
	print(m * (m - 1) * 3)
	t -= 1


def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	if n == 0:
		return 1
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
t = int(input())
c = 0
ans = []
for i in range(t):
	n = int(input())
	digit = list(map(int, input().split()))
	total_dig = 10 - n
	ans.append(int(nCr(total_dig, 2) * nCr(4, 2)))
for i in range(len(ans)):
	print(ans[i])


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	miss = 10 - len(arr)
	miss -= 1
	pairs = miss * (miss + 1) // 2
	print(pairs * 6)


for s in [*open(0)][1::2]:
	k = 10 - int(s)
	print(k * (k - 1) * 3)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	t = 0
	for i in range(10 - n - 1):
		c = i + 1
		t += c * 6
	print(t)


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	q = 10 - m
	if q == 0 or q == 1:
		print(0)
	else:
		s = 0
		for j in range(1, q):
			s += j
		e = s * 6
	print(e)


n = int(input())
for _ in range(n):
	k = int(input())
	k = 10 - k
	s = input()
	f = 0
	for i in range(k):
		f += 6 * i
	print(f)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	m = 10 - n
	ans = m * (m - 1) * 3
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for i in range(1, 10 - n):
		s += i
	print(s * 6)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = 10 - n
	print(3 * b * (b - 1))


for i in range(int(input())):
	n = int(input())
	c = input()
	print((10 - n) * (9 - n) * 3)


t = int(input())
for i in range(t):
	n = int(input())
	numbers = input()
	res = int((10 - n) * (10 - n - 1) / 2)
	print(6 * res)


import math as m
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(m.comb(10 - n, 2) * 6)


from math import ceil
import sys

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

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

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = get_arr()
	n = 10 - n
	print(int(6 * (n * (n - 1)) / 2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n > 8:
		print(0)
	else:
		print(3 * (10 - n) * (10 - n - 1))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(6 * math.factorial(10 - n) // (math.factorial(10 - n - 2) * 2))


for _ in range(int(input())):
	n = int(input())
	a = set(map(int, input().split()))
	k = 10 - len(a)
	print(3 * k * (k - 1))


for i in range(int(input())):
	n = int(input())
	values = list(map(int, input().split()))
	out = 0
	for k in range(0, 10):
		if k not in values:
			out += 1
	print(3 * out * (out - 1))


t = int(input())
l = [0, 216, 168, 126, 90, 60, 36, 18, 6]
for _ in range(t):
	n = int(input())
	s = input()
	print(l[n])


t = int(input())
while t > 0:
	n = int(input())
	vals = input().split()
	cantake = 10 - len(vals)
	ans = 6 * cantake * (cantake - 1) // 2
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	input()
	print(3 * (10 - n) * (9 - n))


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(n):
	n = 10 - n
	x = n * (n - 1) // 2
	return x * 6
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n))


try:
	for _ in range(int(input())):
		n = int(input())
		lst = list(map(int, input().split()))
		print((10 - n) * (10 - n - 1) * 3)
except Exception as e:
	print(e)


for _ in range(int(input())):
	n = int(input())
	lis = input()
	ans = 0
	val = 10 - n
	for i in range(val):
		for j in range(i + 1, val):
			ans += 6
	print(ans)


t = eval(input())
import math
for i in range(t):
	n = eval(input())
	a = list(map(int, input().split()))
	n = 10 - n
	a = math.comb(n, 2)
	print(a * 6)


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	a = inp_arr()
	mp = collections.defaultdict(int)
	for x in a:
		mp[x] = 1
	m = 10 - n
	print(m * (m - 1) * 3)
(tt,) = inp_arr()
for t in range(tt):
	solve()


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]
import math

def solve(n, a):
	use = 10 - n
	return int(use * (use - 1) * (1 / 2) * math.factorial(4) * (1 / 4))
t = ni()
for case in range(t):
	n = ni()
	a = nl()
	print(solve(n, a))


import math
n = int(input())
for i in range(n):
	m = int(input())
	a = list(map(int, input().split()))
	print(int(math.factorial(10 - m) / math.factorial(2) / math.factorial(8 - m) * 6))


import math
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = math.comb(10 - n, 2) * 6
	print(ans)


from math import comb
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l = list(set(l))
	print(comb(10 - len(l), 2) * 6)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = (10 - n) * (9 - n) * 3
	print(s)


def fact(n):
	s = 1
	for i in range(1, n + 1):
		s = s * i
	return s
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = 10 - n
	t = (q - 1) * q // 2
	print(t * 6)


t = int(input())
for t0 in range(t):
	c = int(input())
	h = input()
	c = 10 - c
	n = c * (c - 1)
	r = n * 3
	print(r)


t = int(input())
for t1 in range(t):
	n = int(input())
	a = input()
	k = 10 - n
	print(3 * k * (k - 1))


n = int(input())
for i in range(n):
	b = int(input())
	input()
	print(3 * (10 - b) * (10 - b - 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = 10 - len(a)
	kop = k * (k - 1) / 2
	print(int(kop * 6))


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	variants = 10 - len(b)
	print(variants * (variants - 1) * 3)


t = int(input())

def factorial(n):
	res = 1
	for i in range(2, n + 1):
		res *= i
	return res
for _ in range(t):
	n = int(input())
	unused = set(map(int, input().split()))
	used = set([i for i in range(10) if i not in unused])
	k = len(used)
	print(k * (k - 1) * 3)


def fxn(n):
	return 3 * (9 - n) * (10 - n)
n = int(input())
for i in range(n):
	a = int(input())
	b = len(list(map(int, input().split())))
	print(fxn(b))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	hav = 10 - n
	print(3 * (hav * (hav - 1)))


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	c = 0
	p = []
	for i in range(10):
		p.append(i)
	for k in p:
		if k not in x:
			c += 1
	d = c * (c - 1) * 3
	print(d)


t = int(input())
for x in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	n = 10 - n
	print(n * (n - 1) // 2 * 6)


a = int(input())
for i in range(a):
	b = int(input())
	c = input()
	d = (10 - b) * (9 - b) // 2 * 6
	print(d)


for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print((10 - n) * (10 - n - 1) // 2 * 6)


t = int(input())
for i in range(t):
	n = int(input())
	input()
	q = 10 - n
	print(q * (q - 1) * 3)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(6 * (10 - n) * (9 - n) // 2)


for a in range(int(input())):
	n = int(input())
	ar = input()
	n = 10 - n
	print(n * (n - 1) * 3)


T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in list(input().split(' '))]
	nn = 10 - n
	print(nn * (nn - 1) // 2 * 6)


def main():
	t = int(input())
	for _ in range(t):
		k = int(input())
		arr = input().split()
		res = (10 - k) * (9 - k) * 3
		print(res)
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	val = 10 - n
	ans = val * (val - 1) // 2 * 6
	print(ans)


fac = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	ans = (10 - n) * (9 - n) // 2
	ans = ans * 6
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))

	def factorial(n):
		if n == 0:
			return 1
		else:
			return n * factorial(n - 1)
	value = 3 * factorial(10 - n) / factorial(8 - n)
	print(int(value))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	val = 6

	def nCr(n, r):
		return fact(n) / (fact(r) * fact(n - r))

	def fact(n):
		if n == 0:
			return 1
		res = 1
		for i in range(2, n + 1):
			res = res * i
		return res
	d = nCr(10 - n, 2)
	print(int(val * d))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	notIn = 10 - len(a)
	c = notIn * (notIn - 1) / 2
	print(int(c * 6))


from itertools import combinations
import math
T = int(input())
for i in range(T):
	N_not_used = int(input())
	lst_not_used = list(map(int, input().split()))
	print(math.comb(10 - N_not_used, 2) * 6)