Read problems statements in Russian here 
The Head Chef has received his id from the Association of Byteland . He wants to know the numerical rank of his number among the numbers that can be formed by the exact same digits ( i.e. among numbers having same number of 0's , 1's ... 9's as his id ) .  Note that id's can start with 0 . Given a number, find the rank of the number .

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains a single integer N denoting the id the chef has received .

------ Output ------ 

For each test case, output a single line containing the answer to the given test case . 

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

$1 ≤ T ≤ 10000$
$1 ≤ number of digits in N ≤ 18$

----- Sample Input 1 ------ 
2
276
762
----- Sample Output 1 ------ 
2
6
----- explanation 1 ------ 
Example case 1.The numbers that can be formed with one '2' ; one '7' and one '6' in increasing order are : 
267 
276 
627 
672 
726 
762 
The  rank  for 276 is 2 and rank for 762 is 6.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Combinatorics

Complete search

Mathematics

Ad-hoc
Skill types: Complete search

Starter code:

Solutions:
from collections import *
fact = lambda n: 1 if n == 0 else n * fact(n - 1)
for _ in range(int(input())):
	s = list(map(int, list(filter(str.isdigit, input()))))
	(p, C, ans, d) = (s.copy(), Counter(s), 1, 1)
	p.sort()
	for v in C.values():
		d *= fact(v)
	for c in s:
		i = p.index(c)
		ans += i * fact(len(p) - 1) // d
		d //= C[c]
		C[c] -= 1
		p.pop(i)
	print(ans)


from math import *
from collections import *
f = [factorial(i) for i in range(19)]
for _ in range(int(input())):
	s = list(str(int(input())))
	(C, d, ans, m, n) = (Counter(s), 1, 1, ord(min(s)), len(s))
	for v in C.values():
		d *= f[v]
	for c in s:
		i = sum((C[chr(k)] for k in range(m, ord(c))))
		ans += i * f[n - 1] // d
		d //= C[c]
		C[c] -= 1
		n -= 1
	print(ans)


fact = [1]
for i in range(1, 30):
	fact.append(fact[i - 1] * i)

def calc_count(counts):
	total = 0
	mexrec = 1
	for v in counts.values():
		total += v
		mexrec *= fact[v]
	return fact[total] / mexrec
t = int(input())
for ts in range(t):
	num = int(input())
	ncount = {}
	snum = str(num)
	lnum = len(snum)
	for i in range(lnum):
		ncount[int(snum[i])] = ncount.get(int(snum[i]), 0) + 1
	ans = 0
	tcount = ncount
	for i in range(lnum):
		dig = int(snum[i])
		for k in ncount.keys():
			if k < dig:
				tcount[k] -= 1
				ans += calc_count(tcount)
				tcount[k] += 1
		tcount[dig] -= 1
		if tcount[dig] == 0:
			del tcount[dig]
	print(int(ans + 1))


from collections import *

def fact(n):
	if n == 0:
		return 1
	return n * fact(n - 1)
for _ in range(int(input())):
	s = list(map(int, list(input())))
	(p, C, ans, d) = (s.copy(), Counter(s), 1, 1)
	p.sort()
	for v in C.values():
		d *= fact(v)
	for c in s:
		i = p.index(c)
		ans += i * fact(len(p) - 1) // d
		d //= C[c]
		C[c] -= 1
		p.pop(i)
	print(ans)


from math import *
from collections import *
f = [factorial(i) for i in range(0, 19)]
for _ in range(int(input())):
	s = list(str(int(input())))
	(p, C, ans, d) = (sorted(s), Counter(s), 1, 1)
	for v in C.values():
		d *= f[v]
	for c in s:
		i = p.index(c)
		ans += i * f[len(p) - 1] // d
		d //= C[c]
		C[c] -= 1
		p.pop(i)
	print(ans)


from collections import *
fact = lambda n: 1 if n == 0 else n * fact(n - 1)
for _ in range(int(input())):
	s = list(str(int(input())))
	(p, C, ans, d) = (sorted(s), Counter(s), 1, 1)
	for v in C.values():
		d *= fact(v)
	for c in s:
		i = p.index(c)
		ans += i * fact(len(p) - 1) // d
		d //= C[c]
		C[c] -= 1
		p.pop(i)
	print(ans)


def fact(x):
	if x == 0 or x == 1:
		return 1
	p = 1
	for i in range(1, x + 1):
		p *= i
	return p

def cal(n, d, rank, total, prod):
	while True:
		if total == 1:
			rank[0] += 1
			break
		key = n // 10 ** (total - 1)
		fval = fact(total - 1)
		for i in d:
			if i < key:
				temp = prod
				temp = temp / fact(d[i]) * fact(d[i] - 1)
				rank[0] += fval / temp
		prod = prod / fact(d[key]) * fact(d[key] - 1)
		d[key] -= 1
		if d[key] == 0:
			d.pop(key)
		n = n % 10 ** (total - 1)
		total -= 1
for _ in range(int(input())):
	n = int(input())
	num = n
	d = {}
	total = 0
	if n == 0:
		print(1)
		continue
	while n > 0:
		if n % 10 not in d:
			d[n % 10] = 1
		else:
			d[n % 10] += 1
		n = n // 10
		total += 1
	prod = 1
	for i in d:
		prod *= fact(d[i])
	rank = [0]
	cal(num, d, rank, total, prod)
	print(int(rank[0]))