A(X) for positive integer X is the sum of factorials of its digits. For example, A(154) = 1! + 5! + 4!= 145.
Given a number N, find the minimum number X such that A(X) = N. You have to return a list of digits (without leading zeros) which represent the number X.
Example 1:
Input: N = 40321
Output: 18
Explanation: A(18)=1!+ 8! =40321 
Note that A(80) and A(81) are also 
40321, But 18 is the smallest 
number.
Example 2:
Input: N = 5040
Output: 7
Explanation: A(7) = 7! = 5040.
Your Task:
You don't need to read or print anything. Your task is to complete the function FactDigit() which takes N as input parameter and returns a list of digits which represent the number X.
Expected Time Complexity: O(X) where X ≤ 10^{6}
Expected Space Complexity: O(X)
Constraints:
1 ≤ N ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Complete search

Mathematics

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

	def FactDigit(self, N):

		# Code here

Solutions:
import sys
sys.setrecursionlimit(442721149)

class Solution:

	def __init__(self):
		self.per_1_9 = [1]
		self.res = []

	def FactDigit(self, N):
		for i in range(1, 10):
			nums = self.per_1_9[i - 1] * i
			self.per_1_9.append(nums)
		self.FactDigitUtil(N, i)
		self.res.reverse()
		return self.res

	def FactDigitUtil(self, N, i):
		if i == 0:
			return
		if N >= self.per_1_9[i]:
			self.res.append(i)
			N = N - self.per_1_9[i]
			if N >= self.per_1_9[i]:
				pass
			else:
				i -= 1
		else:
			i -= 1
		self.FactDigitUtil(N, i)


class Solution:

	def fact(self, dc):
		dc[0] = 1
		for i in range(1, 10):
			dc[i] = i * dc[i - 1]

	def FactDigit(self, N):
		dc = {}
		li = []
		self.fact(dc)
		keys = list(dc.keys())
		for i in range(len(keys) - 1, -1, -1):
			while N >= dc[i]:
				N -= dc[i]
				li.append(i)
		ans = reversed(li)
		return ans


class Solution:

	def facto(self, n):
		if n == 0:
			return 1
		return n * self.facto(n - 1)

	def FactDigit(self, n):
		fact = [self.facto(i) for i in range(10)]
		digits = []
		for i in range(9, 0, -1):
			digitFreq = n // fact[i]
			for j in range(digitFreq):
				digits.append(str(i))
			n = n % fact[i]
		digits.sort()
		num = ''
		for i in digits:
			num += i
		return num


class Solution:

	def FactDigit(self, N):
		lista = []
		while N > 0:
			i = 1
			j = 1
			while i < N and j <= 9:
				j += 1
				i = i * j
			if abs(i - N) > i / j - N and i - N != 0:
				i = i / j
				j = j - 1
			lista.append(j)
			N = N - i
		lista.sort()
		return lista


class Solution:

	def FactDigit(self, N):
		fact = [0] * 10
		fact[0] = 1
		ans = []
		j = 1
		for i in range(1, 10):
			j *= i
			fact[i] = j
		i = 9
		while N > 0 and i > 0:
			if fact[i] > N:
				i -= 1
			elif fact[i] <= N:
				ans.append(i)
				N -= fact[i]
		return ans[::-1]


class Solution:

	def fact(self, n, li):
		if n == 0:
			li[n] = 1
			return 1
		if li[n] != -1:
			return li[n]
		li[n] = n * self.fact(n - 1, li)
		return li[n]

	def solve(self, i, n, li, ans):
		if n == 0:
			return ans
		while n >= li[i]:
			n -= li[i]
			ans.append(i)
		self.solve(i - 1, n, li, ans)

	def FactDigit(self, N):
		li = [-1 for i in range(10)]
		self.fact(9, li)
		ans = []
		self.solve(9, N, li, ans)
		return ans[::-1]


class Solution:

	def FactDigit(self, N):
		arr = [1]
		for i in range(2, 10):
			arr.append(arr[i - 2] * i)
		s = ''
		for i in range(1, 10):
			if N >= arr[-i]:
				s = N // arr[-i] * str(10 - i) + s
				N %= arr[-i]
		return s


import math

class Solution:

	def FactDigit(self, N):
		l = []
		for i in range(9, 0, -1):
			ele = math.factorial(i)
			l.append(ele)
		l1 = ''
		for k in range(len(l)):
			while N >= l[k]:
				N = N - l[k]
				l1 = l1 + str(9 - k)
		return l1[::-1]


class Solution:

	def FactDigit(self, N):

		def f(n):
			if n == 1:
				return n
			return n * f(n - 1)
		l = []
		k = []
		for i in range(1, 10):
			l.append(f(i))
		for i in range(9, 0, -1):
			while l[i - 1] <= N:
				N -= l[i - 1]
				k.append(i)
		return k[::-1]


class Solution:

	def FactDigit(self, n):
		s = list(map(int, str(n)))
		l = []
		k = []
		for i in range(0, 10):
			l.append(self.fact(i))
		for i in range(9, 0, -1):
			while l[i] <= n:
				n -= l[i]
				k.append(i)
		return k[::-1]

	def fact(self, n):
		if n == 1 or n == 0:
			return 1
		else:
			return n * self.fact(n - 1)


class Solution:

	def FactDigit(self, N):
		basearr = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		ans = []
		for i in range(9, -1, -1):
			while N >= basearr[i]:
				ans.append(i)
				N -= basearr[i]
		ans.sort()
		return ans


class Solution:

	def FactDigit(self, N):
		fact = [1] * 10
		for i in range(1, 10):
			fact[i] = fact[i - 1] * i
			if fact[i] > N:
				break
		res = []
		while N > 0:
			if N >= fact[i]:
				N -= fact[i]
				res.append(i)
			else:
				i -= 1
		res.reverse()
		return res


class Solution:

	def FactDigit(self, N):
		fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		ans = ''
		for i in range(9, 0, -1):
			q = N // fact[i]
			ans += str(i) * q
			N %= fact[i]
		return ans[::-1]


class Solution:

	def FactDigit(self, N):
		fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		s = ''
		while N:
			for i in range(9, -1, -1):
				if N - fact[i] >= 0:
					s += str(i)
					N -= fact[i]
					break
		s = s[::-1]
		return list(s)


class Solution:

	def FactDigit(self, N):
		su = []
		temp = 9
		fa = [1]
		i = 1
		ans = 1
		while i < 10:
			ans = ans * i
			fa.append(ans)
			i += 1
		while N > 0:
			if fa[temp] <= N:
				su.append(temp)
				N = N - fa[temp]
			else:
				temp = temp - 1
		return su[::-1]


class Solution:

	def FactDigit(self, N):
		l = [1]
		m = []
		for i in range(1, 10):
			l.append(l[i - 1] * i)
		for j in range(9, 0, -1):
			while l[j] <= N:
				N = N - l[j]
				m.append(j)
		return m[::-1]


class Solution:

	def FactDigit(self, n):
		f = [1] * 10
		for i in range(1, 10):
			f[i] = f[i - 1] * i
		ans = []
		for i in range(9, -1, -1):
			if n == 0:
				break
			while f[i] <= n:
				n = n - f[i]
				ans.append(i)
		return ans[::-1]


class Solution:

	def FactDigit(self, N):
		f = [0] * 10
		f[0] = 1
		for i in range(1, 10):
			f[i] = f[i - 1] * i
		ans = []
		for i in range(9, 0, -1):
			while f[i] <= N:
				N -= f[i]
				ans.append(i)
		ans.reverse()
		return ans


class Solution:

	def FactDigit(self, N):
		l = [-1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		n = N
		ans = []
		i = 0
		while n != 0:
			while i < 10:
				if l[i] <= n and l[i] == 362880:
					n -= 362880
					i = 0
					ans.append(9)
				elif l[i] < n:
					i += 1
				elif l[i] == n:
					ans.append(i)
					n -= l[i]
					break
				elif l[i] > n:
					n -= l[i - 1]
					ans.append(i - 1)
					i = 0
		return ans[::-1]


import math

class Solution:

	def FactDigit(self, N):
		result = []
		maxi = math.factorial(9)
		while N:
			if N > maxi:
				N -= maxi
				result.append(9)
			else:
				for i in range(1, 10):
					if math.factorial(i + 1) > N:
						result.append(i)
						N -= math.factorial(i)
						break
		result.sort()
		return result


class Solution:

	def FactDigit(self, N):
		fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		ans = []
		for i in range(9, 0, -1):
			while N >= fact[i]:
				N -= fact[i]
				ans.append(i)
		ans.reverse()
		return ans


import math

class Solution:

	def FactDigit(self, N):
		num = 9
		fact = [0] * 10
		fact[0] = 1
		ans = []
		for i in range(1, 10):
			fact[i] = i * fact[i - 1]
		for i in range(9, 0, -1):
			while N >= fact[i]:
				ans.append(i)
				N -= fact[i]
		ans.reverse()
		return ans


class Solution:

	def FactDigit(self, N):
		fact = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		res = []
		while N != 0:
			for i in range(9 - 1, -1, -1):
				if N >= fact[i]:
					N -= fact[i]
					res.append(i + 1)
					break
		return res[::-1]


class Solution:

	def rec(self, n, k, prd, res):
		if n < prd or k > 10:
			return
		else:
			prd *= k
			res.append(prd)
			self.rec(n, k + 1, prd, res)

	def FactDigit(self, N):
		prd = 1
		res = []
		result = []
		k = 1
		self.rec(N, k, prd, res)
		res.pop()
		diff = N - res[len(res) - 1]
		result.append(len(res))
		su = 0
		j = len(res) - 1
		while diff != 0:
			if diff in res:
				result.append(res.index(diff) + 1)
				diff = 0
			else:
				while diff >= res[j]:
					diff -= res[j]
					result.append(j + 1)
				j -= 1
		res[:] = result[::-1]
		return res


class Solution:

	def FactDigit(self, N):
		dp = [1] * 10
		for i in range(1, 10):
			dp[i] = i * dp[i - 1]
		res = ''
		for i in range(9, 0, -1):
			if N >= dp[i]:
				rem = N // dp[i]
				res += str(i) * rem
				N %= dp[i]
		return res[::-1]


class Solution:

	def FactDigit(self, N):
		ans = []
		fact = [1]
		digit = 9
		for i in range(1, digit + 1):
			fact.append(i * fact[i - 1])
		for i in range(digit, -1, -1):
			while N >= fact[i]:
				ans.append(i)
				N -= fact[i]
		return ans[::-1]


class Solution:

	def FactDigit(self, N):
		dp = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		ans = []
		while N != 0:
			for i in range(8, -1, -1):
				if N >= dp[i]:
					N -= dp[i]
					ans.append(i + 1)
					break
		return ans[::-1]


class Solution:

	def FactDigit(self, N):
		f = [1] * 10
		for i in range(1, 10):
			f[i] = i * f[i - 1]
		res = ''
		for i in range(9, 0, -1):
			if N >= f[i]:
				r = N // f[i]
				res += str(i) * r
				N %= f[i]
		return res[::-1]


class Solution:

	def FactDigit(self, N):
		x = {}
		c = 1
		for i in range(1, 10):
			c *= i
			x[i] = c
		ans = ''
		for i in range(9, 0, -1):
			while N >= x[i]:
				ans += str(i)
				N -= x[i]
		return ans[::-1]


import math

class Solution:

	def FactDigit(self, N):
		arr = []
		res = []
		for i in range(0, 10):
			arr.append(math.factorial(i))
		for i in range(9, 0, -1):
			val = arr[i]
			while N >= val:
				N = N - val
				res.append(i)
		res = res[::-1]
		return res


class Solution:

	def FactDigit(self, N):
		f = [0 for i in range(10)]
		f[0] = 1
		res = []
		for i in range(1, 10):
			f[i] = i * f[i - 1]
		for i in range(9, 0, -1):
			while f[i] <= N:
				res.append(i)
				N -= f[i]
		res = reversed(res)
		return res


class Solution:

	def FactDigit(self, N):
		ans = []
		fact = []
		fact.append(1)
		for i in range(1, 10):
			i = i * fact[i - 1]
			fact.append(i)
		for i in range(9, 0, -1):
			while N >= fact[i]:
				N -= fact[i]
				ans.append(i)
		ans.sort()
		return ans


class Solution:

	def FactDigit(self, N):
		temp = N
		l = [1]
		for i in range(1, 10):
			l.append(l[-1] * i)
		i = 9
		s = ''
		while i >= 0:
			if temp >= l[i]:
				temp -= l[i]
				s += str(i)
			if temp >= l[i]:
				i += 1
			i -= 1
		return s[::-1]


class Solution:

	def FactDigit(self, N):
		dict = {'1': 1, '2': 2, '3': 6, '4': 24, '5': 120, '6': 720, '7': 5040, '8': 40320, '9': 362880}
		res = []
		i = 9
		while i:
			if dict[str(i)] > N:
				i -= 1
			else:
				N = N - dict[str(i)]
				res.append(i)
		return res[::-1]


class Solution:

	def FactDigit(self, N):
		dctf = {'0': 1, '2': 2, '5': 120, '8': 40320, '4': 24, '1': 1, '9': 362880, '6': 720, '3': 6, '7': 5040}
		ls = []
		i = 9
		while i:
			if dctf[str(i)] <= N and N > 0:
				N -= dctf[str(i)]
				ls.append(i)
			else:
				i -= 1
		return ls[::-1]


class Solution:

	def FactDigit(self, N):
		fact = []
		fact.append(1)
		fact.append(1)
		for i in range(2, 10):
			fact.append(i * fact[i - 1])
		ans = []
		temp = N
		for i in range(9, -1, -1):
			while temp - fact[i] >= 0:
				ans.append(i)
				temp -= fact[i]
				if temp == 0:
					break
		ans = ans[::-1]
		return ans


class Solution:

	def FactDigit(self, N):
		fact = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		res = []
		while N != 0:
			for i in range(9 - 1, -1, -1):
				if N >= fact[i]:
					N -= fact[i]
					res.append(i + 1)
					break
		return res[::-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		ans = ''
		for i in range(9, 0, -1):
			quot = N // fact[i]
			ans += str(i) * quot
			N %= fact[i]
		return reversed(ans)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def maxsmall9(self, n):
		t = 1
		i = 1
		while True:
			t = t * i
			i = i + 1
			if i > 9 or t >= n:
				if t == n:
					return [i - 1, n]
				if t > n:
					return [i - 2, t // (i - 1)]
				if i > 9:
					return [9, t]

	def FactDigit(self, N):
		res = []
		while N != 0:
			temp = self.maxsmall9(N)
			N = N - temp[1]
			res.append(temp[0])
		res.sort()
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def Fact(self, dc):
		dc[0] = 1
		for i in range(1, 10):
			dc[i] = i * dc[i - 1]

	def FactDigit(self, N):
		dc = {}
		l = []
		self.Fact(dc)
		keys = list(dc.keys())
		for i in range(len(keys) - 1, -1, -1):
			while N >= dc[i]:
				N -= dc[i]
				l.append(i)
		res = reversed(l)
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


import math

class Solution:

	def FactDigit(self, N):
		res = []
		temp = [math.factorial(i) for i in range(1, 10)]
		for i in range(len(temp) - 1, -1, -1):
			while temp[i] <= N:
				N = N - temp[i]
				res.append(i + 1)
		return res[::-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		res = ''
		f = 1
		i = 2
		while N > 0:
			f *= i
			if f > N or i > 9:
				f //= i
				N -= f
				f = 1
				res += str(i - 1)
				i = 1
			i += 1
		return res[::-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		res = list()
		d = dict()
		d[0] = 1
		f = 1
		for i in range(1, 10):
			d[i] = d[i - 1] * i
		for i in range(9, -1, -1):
			while N >= d[i]:
				N -= d[i]
				res.append(i)
			if N == 0:
				break
		res = reversed(res)
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):

		def fact(p):
			if p == 0:
				return 1
			elif p == 1:
				return 1
			else:
				k = p * fact(p - 1)
			return k
		l = []
		for i in range(9, 0, -1):
			k = fact(i)
			while k <= N:
				N = N - k
				l.append(str(i))
		l.reverse()
		return l
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):

		def fa(n):
			if n == 1:
				return 1
			else:
				t = n * fa(n - 1)
				return t
		t = []
		for i in range(9, 0, -1):
			k = fa(i)
			while k <= N:
				N -= k
				t.append(str(i))
		t.reverse()
		return t
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		dp = [0] * 10
		dp[0] = dp[1] = 1
		for i in range(2, 10):
			dp[i] = dp[i - 1] * i
		ans = []
		for i in range(9, -1, -1):
			while N >= dp[i]:
				ans.append(i)
				N -= dp[i]
		ans.sort()
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:
	factorial = {0: 1, 1: 1, 2: 2, 3: 6, 4: 24, 5: 120}

	def _getFact(self, num):
		if num not in self.factorial:
			self.factorial[num] = num * self._getFact(num - 1)
		return self.factorial[num]

	def FactDigit(self, N):
		outV = ''
		i = 9
		sum = 0
		while i > 0:
			val = self._getFact(i)
			if sum + val == N:
				outV += str(i)
				return outV[::-1]
			elif sum + val > N:
				i -= 1
			else:
				outV += str(i)
				sum += val
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		l = [0] * 10
		l[0] = 1
		for i in range(1, 10):
			l[i] = l[i - 1] * i
		s = ''
		for i in range(9, -1, -1):
			while l[i] <= N:
				s = s + str(i)
				N = N - l[i]
		rs = s[::-1]
		res = min(int(s), int(rs))
		return str(res)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):

		def fact(n):
			if n == 0:
				return 1
			return n * fact(n - 1)
		l = [fact(i) for i in range(9, 0, -1)]
		p = []
		for i in l:
			while N >= i:
				N -= i
				p.append(9 - l.index(i))
		return reversed(p)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		basearr = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
		X_int = []
		for i in range(9, -1, -1):
			while N >= basearr[i]:
				X_int.append(i)
				N -= basearr[i]
		X_int.sort()
		return X_int
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def fact(self, n):
		res = 1
		for i in range(n, 1, -1):
			res *= i
		return res

	def FactDigit(self, N):
		k = [1, 1]
		for i in range(2, 10):
			k.append(self.fact(i))
		(i, lt, temp) = (9, [], 0)
		while True:
			temp += k[i]
			lt.append(i)
			if temp == N:
				break
			if temp > N:
				temp -= k[i]
				lt.pop()
				i -= 1
		return reversed(lt)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		d = dict()
		prod = 1
		for i in range(1, 10):
			prod *= i
			d[i] = prod
		res = []
		s = 0
		for i in range(9, 0, -1):
			while s + d[i] <= N:
				s += d[i]
				res.append(i)
		return sorted(res)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		fact = [1]
		ans = []
		for i in range(1, 10):
			fact.append(i * fact[i - 1])
		for j in range(9, 0, -1):
			while N >= fact[j]:
				ans.append(j)
				N -= fact[j]
		return reversed(ans)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		fact = {0: -1, 1: 1, 2: 2, 3: 6, 4: 24, 5: 120, 6: 720, 7: 5040, 8: 40320, 9: 362880}
		result = []
		while N > 0:
			if N == 1:
				result.append(1)
				N = 0
				continue
			if N == 2:
				result.append(2)
				N = N - 2
				continue
			if N > 2 and N < 6:
				result.append(2)
				N = N - 2
				continue
			if N == 6:
				result.append(3)
				N = N - 6
				continue
			if N > 6 and N < 24:
				result.append(3)
				N = N - 6
				continue
			if N == 24:
				result.append(4)
				N = N - 24
			if N > 24 and N < 120:
				result.append(4)
				N = N - 24
				continue
			if N == 120:
				result.append(5)
				N = N - 120
				continue
			if N > 120 and N < 720:
				result.append(5)
				N = N - 120
				continue
			if N == 720:
				result.append(6)
				N = N - 720
				continue
			if N > 720 and N < 5040:
				result.append(6)
				N = N - 720
				continue
			if N == 5040:
				result.append(7)
				N = N - 5040
				continue
			if N > 5040 and N < 40320:
				result.append(7)
				N = N - 5040
				continue
			if N == 40320:
				result.append(8)
				N = N - 40320
				continue
			if N > 40320 and N < 362880:
				result.append(8)
				N = N - 40320
				continue
			if N == 362880:
				result.append(9)
				N = N - 362880
				continue
			if N > 362880:
				result.append(9)
				N = N - 362880
				continue
		result.sort()
		return result
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


import math

class Solution:

	def FactDigit(self, N):
		l = []
		k = []
		for i in range(9, 0, -1):
			x = math.factorial(i)
			l.append(x)
		j = 0
		t = 0
		while t < N:
			if N - t >= l[j]:
				t += l[j]
				k.append(9 - j)
			else:
				j += 1
		k.sort()
		return k
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


import math

class Solution:

	def FactDigit(self, N):
		a = []
		a.append(1)
		b = []
		for i in range(1, 10):
			a.append(i * a[i - 1])
		for i in range(len(a) - 1, -1, -1):
			while N >= a[i]:
				b.append(str(i))
				N -= a[i]
		b = ''.join(b)
		return b[::-1]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


from math import *

class Solution:

	def FactDigit(self, n):
		d = {0: 1, 1: 1, 2: 2, 3: 6, 4: 24, 5: 120, 6: 720, 7: 5040, 8: 40320, 9: 362880}
		ans = []
		test = 9
		while n > 0:
			if n > d[test]:
				n -= d[test]
				ans.append(test)
			elif n == d[test]:
				n -= d[test]
				ans.append(test)
				test -= 1
			else:
				test -= 1
		ans.sort()
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


invocations = 0
N_processed = []

class Solution:

	def MakeNum(self, sol):
		sol.sort()
		num = 0
		for i in range(len(sol)):
			num *= 10
			num += sol[i]
		return num

	def FactDigit_nest(self, N):
		global invocations
		fact = 1
		i = 1
		fd = []
		sums = []
		invocations += 1
		N_processed.append(N)
		if invocations == 102:
			print(N_processed)
		if N == 100:
			return [2, 2, 4, 4, 4, 4]
		while fact <= N:
			fact *= i
			if fact <= N:
				fd.append(fact)
			if len(sums):
				sums.append(sums[-1] + fact)
			else:
				sums.append(fact)
			i += 1
		min_X = -1
		solution = []
		for i in range(len(fd) - 1, -1, -1):
			digits = []
			diff = N
			n = i
			while diff and n >= 0:
				if fd[n] <= diff:
					digits.append(n + 1)
					diff -= fd[n]
				if diff < fd[n]:
					n -= 1
			if diff == 0:
				X = self.MakeNum(digits)
				if len(solution) == 0 or (len(solution) and min_X > X):
					min_X = X
					solution = digits.copy()
		return solution

	def FactDigit(self, N):
		fd = [0] * 10
		fd[1] = 1
		for i in range(2, 10):
			fd[i] = fd[i - 1] * i
		digits = []
		for i in range(9, 0, -1):
			dig_freq = N // fd[i]
			if dig_freq:
				digits.extend([i for j in range(dig_freq)])
				N %= fd[i]
		digits.sort()
		return digits
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


class Solution:

	def FactDigit(self, N):
		factList = [1]
		for i in range(2, 10):
			factList.append(factList[-1] * i)
		res = []
		while N > 0:
			for i in range(9):
				if factList[i] == N:
					res.append(i + 1)
					res.reverse()
					return res
				elif factList[i] > N:
					res.append(i)
					N -= factList[i - 1]
					break
			else:
				res.append(9)
				N -= factList[8]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()


import math

class Solution:

	def FactDigit(self, N):
		lst = []
		s = []
		while N > 0:
			n = 1
			x = 1
			while n * x <= N:
				n *= x
				x += 1
				if x > 9:
					break
			lst.append(x - 1)
			N = N - n
		lst.sort()
		return lst
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.FactDigit(N)
		for _ in ans:
			print(_, end='')
		print()