Given a number s(in string form). Find the Smallest number (Not leading Zeros) which can be obtained by rearranging the digits of given number.
 
Example 1:
Input: s = "846903"
Output: 304689
Explanation: 304689 is the smallest number
by rearranging the digits.
Example 2:
Input: s = "55010"
Output: 10055
Explanation: 10055 is the smallest number 
by rearranging the digts.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function minimum_number() which takes the number as input parameter and returns the smallest number than can be formed without leading zeros by rearranging the digits of the number.
 
Expected Time Complexity: O(N * log(N)) where N is the number of digits of the given number
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def minimum_Number(self, s):

		# Code here

Solutions:
class Solution:

	def minimum_Number(self, s):
		l = list(s)
		l.sort()
		for i in range(len(l)):
			if int(l[i]) > 0:
				(l[0], l[i]) = (l[i], l[0])
				break
		n = ''
		for i in l:
			n += i
		return n


class Solution:

	def minimum_Number(self, s):
		d = {}
		for i in s:
			i = int(i)
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		t = list(d.keys())
		t.sort()
		if len(t) == 1:
			return str(t[0]) * d[t[0]]
		res = str(t[1] * 10 + t[0])
		(d[t[0]], d[t[1]]) = (d[t[0]] - 1, d[t[1]] - 1)
		for i in t:
			res += str(i) * d[int(i)]
		return res


class Solution:

	def minimum_Number(self, s):
		sort = sorted(s)
		s = ''
		i = 0
		while sort[i] == '0' and i < len(sort) - 1:
			i += 1
		if i == len(sort):
			for ele in sort:
				s += ele
		temp = sort[0]
		sort[0] = sort[i]
		sort[i] = temp
		for ele in sort:
			s += ele
		return s


class Solution:

	def minimum_Number(self, s):
		arr = []
		new = []
		s = list(s)
		for i in s:
			if int(i) == 0:
				new.append(int(i))
			else:
				arr.append(int(i))
		if len(new) == len(s):
			return ''.join(s)
		arr.sort()
		new1 = [arr.pop(0)]
		new1.extend(new)
		new1.extend(arr)
		ans = ''
		for i in new1:
			ans += str(i)
		ans = int(ans)
		return ans


class Solution:

	def minimum_Number(self, s):
		j = sorted(s)
		p = ''
		if j[0] != '0':
			return p.join(j)
		else:
			for i in range(len(j)):
				if j[i] != '0':
					temp = j[0]
					j[0] = j[i]
					j[i] = temp
					break
		return p.join(j)


class Solution:

	def minimum_Number(self, s):
		m = sorted(s)
		for i in range(len(m)):
			if int(m[i]) > 0:
				(m[0], m[i]) = (m[i], m[0])
				break
		sr = ''
		for i in m:
			sr += i
		return sr


class Solution:

	def minimum_Number(self, s):
		lst = list(s)
		lst.sort()
		tmp = ''
		for (i, n) in enumerate(lst):
			if n != '0':
				tmp = lst.pop(i)
				break
		return str(tmp) + ''.join(lst)


class Solution:

	def minimum_Number(self, s):
		l = list(s)
		l.sort()
		tmp = ''
		for (i, ele) in enumerate(l):
			if ele != '0':
				tmp = str(l.pop(i))
				break
		return str(tmp) + ''.join(l)


class Solution:

	def minimum_Number(self, s):
		n = len(s)
		lst = list(map(int, s))
		lst.sort()
		for i in range(n):
			if lst[i] != 0:
				(lst[0], lst[i]) = (lst[i], lst[0])
				break
		ans = ''
		for i in lst:
			ans += str(i)
		return ans


import functools

class Solution:

	def minimum_Number(self, s):
		c = 0
		arr = []
		for i in s:
			if i != 0:
				arr.append(i)
			if i == '0':
				c += 1
		if c == len(s):
			return s

		def fuc(a, b):
			if a + b > b + a:
				return 1
			else:
				return -1
		arr.sort()
		news = str(int(''.join(arr)))
		if c == 0:
			return news
		else:
			return news[0] + '0' * c + news[1:]


class Solution:

	def minimum_Number(self, s):
		num = sorted(s)
		t = 0
		for i in num:
			if i == '0':
				t += 1
			else:
				break
		num = num[t:]
		if len(num) > 0:
			x = num[0]
		else:
			return '0' * t
		num = ['0'] * t + num[1:]
		num.insert(0, x)
		return ''.join(num)


class Solution:

	def minimum_Number(self, s):
		g = s.count('0')
		l = s.replace('0', '')
		if len(l) == 0:
			return s
		l = sorted(l)
		l.sort()
		h = [l[0]]
		for i in range(g):
			h.append('0')
		for i in range(1, len(l)):
			h.append(l[i])
		return ''.join(h)


class Solution:

	def minimum_Number(self, s):
		x = [i for i in s]
		x.sort()
		c = 0
		for i in range(len(x)):
			if x[i] != '0':
				c = i
				break
		(x[0], x[c]) = (x[c], x[0])
		return ''.join(x)


class Solution:

	def minimum_Number(self, s):
		snum = sorted(list(s))
		czero = snum.count('0')
		if czero == len(snum):
			return s
		snum[0] = snum[czero]
		snum[czero] = '0'
		return ''.join(snum)


class Solution:

	def minimum_Number(self, s):
		lst = []
		for c in s:
			lst.append(c)
		lst.sort()
		n = len(lst)
		i = 0
		while i < n and lst[i] == '0':
			i += 1
		if i == n:
			return int(''.join(lst))
		else:
			(lst[0], lst[i]) = (lst[i], lst[0])
			return int(''.join(lst))


class Solution:

	def minimum_Number(self, s):
		s = sorted(s)
		ans = ''
		temp = ''
		flag = 1
		for i in s:
			if i == '0':
				temp = temp + i
				flag = 0
			else:
				ans = ans + i
				if flag == 0:
					ans = ans + temp
					flag = 1
		if len(ans) == 0:
			return temp
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.minimum_Number(s)
		print(ans)


class Solution:

	def minimum_Number(self, s):
		l = list(s)
		l.sort()
		for i in range(len(l)):
			if int(l[i]) > 0:
				(l[0], l[i]) = (l[i], l[0])
				break
		n = ''
		for i in l:
			n += i
		return n
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.minimum_Number(s)
		print(ans)


class Solution:

	def minimum_Number(self, s):
		x = list(sorted(s))
		k = ''
		for i in x:
			if i != '0':
				k += i
				break
		if len(k) == 0:
			return s
		x.remove(k[0])
		for i in x:
			k += i
		return k
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.minimum_Number(s)
		print(ans)


class Solution:

	def minimum_Number(self, s):
		arr = list(s)
		arr.sort()
		for i in range(len(arr)):
			if arr[i] != '0':
				temp = arr[i]
				arr.pop(i)
				break
		if len(arr) == len(s):
			return s
		else:
			return temp + ''.join(arr)


class Solution:

	def minimum_Number(self, s):
		res = [int(x) for x in str(s)]
		mo = ''
		res.sort()
		if res[len(res) - 2] == 0:
			res.sort(reverse=True)
			for s in res:
				mo = mo + str(s)
			return int(mo)
		if res[0] == 0:
			for i in range(len(res) - 1):
				if res[i] > 0:
					res[0] = res[i]
					res[i] = 0
					break
		for s in res:
			mo = mo + str(s)
		return int(mo)


class Solution:

	def minimum_Number(self, s):
		s = list(s)
		s.sort()
		ind = 0
		leng = len(s)
		while ind < leng and s[ind] == '0':
			ind += 1
		if ind == leng:
			return int(''.join(s))
		p = s.pop(ind)
		s.insert(0, p)
		return int(''.join(s))


class Solution:

	def minimum_Number(self, s):
		dic = {}
		for el in range(10):
			dic[str(el)] = 0
		if s[0] != '-':
			for el in s:
				dic[el] += 1
			newS = ''
			for el in range(1, 10):
				newS += str(el) * dic[str(el)]
			if dic['0'] != 0 and len(newS) > 0:
				newS = newS[0] + '0' * dic['0'] + newS[1:]
			elif dic['0'] != 0 and len(newS) == 0:
				newS += '0' * dic['0']
			return newS
		else:
			for el in s[1:]:
				dic[el] += 1
			newS = ''
			for el in range(9, -1, -1):
				newS += str(el) * dic[str(el)]
			newS = '-' + newS
			return newS


class Solution:

	def minimum_Number(self, s):
		s = sorted(s)
		if s[-1] == '0':
			return ''.join(s)
		i = 0
		while s[i] == '0':
			i += 1
		(s[i], s[0]) = (s[0], s[i])
		return ''.join(s)


class Solution:

	def minimum_Number(self, s):
		n = len(s)
		s = list(s)
		s = sorted(s)
		i = 0
		while i < n - 1 and s[i] == '0':
			i += 1
		if i == 0:
			return ''.join(s)
		else:
			(s[0], s[i]) = (s[i], s[0])
		return ''.join(s)


class Solution:

	def minimum_Number(self, s):
		lst = list(s)
		num = sorted(lst)
		num = ''.join(num)
		num = list(num)
		for i in range(len(num)):
			if num[i] == '0':
				continue
			(num[i], num[0]) = (num[0], num[i])
			return ''.join(num)
		return ''.join(num)


class Solution:

	def minimum_Number(self, n):
		arr = sorted([int(i) for i in list(str(n))])
		zcount = arr.count(0)
		if zcount == 0:
			return int(''.join(arr))
		elif zcount == len(arr):
			return 0
		else:
			s = str(arr[zcount])
			for _ in range(zcount):
				s += '0'
			for i in arr[zcount + 1:]:
				s += str(i)
			return int(s)


import heapq

class Solution:

	def minimum_Number(self, s):
		s = list(s)
		s.sort()
		s.append('-1')
		i = 0
		while s[i] == '0':
			i += 1
		if i == len(s) - 1:
			return 0
		s.pop()
		(s[0], s[i]) = (s[i], s[0])
		return ''.join(s)


class Solution:

	def minimum_Number(self, s):
		n = len(s)
		ls = list(s)
		ls.sort()
		i = 0
		while i < n and ls[i] == '0':
			i += 1
		if i < n:
			(ls[0], ls[i]) = (ls[i], ls[0])
		return ''.join(ls)