You are given a string $s$. You need to find two non-empty strings $a$ and $b$ such that the following conditions are satisfied:

Strings $a$ and $b$ are both subsequences of $s$.

For each index $i$, character $s_i$ of string $s$ must belong to exactly one of strings $a$ or $b$.

String $a$ is lexicographically minimum possible; string $b$ may be any possible string.

Given string $s$, print any valid $a$ and $b$.

Reminder:

A string $a$ ($b$) is a subsequence of a string $s$ if $a$ ($b$) can be obtained from $s$ by deletion of several (possibly, zero) elements. For example, "dores", "cf", and "for" are subsequences of "codeforces", while "decor" and "fork" are not.

A string $x$ is lexicographically smaller than a string $y$ if and only if one of the following holds:

$x$ is a prefix of $y$, but $x \ne y$;

in the first position where $x$ and $y$ differ, the string $x$ has a letter that appears earlier in the alphabet than the corresponding letter in $y$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first and only line of each test case contains one string $s$ ($2 \le |s| \le 100$ where $|s|$ means the length of $s$). String $s$ consists of lowercase Latin letters.


-----Output-----

For each test case, print the strings $a$ and $b$ that satisfy the given conditions. If there are multiple answers, print any.


-----Examples-----

Input
3
fc
aaaa
thebrightboiler
Output
c f
a aaa
b therightboiler


-----Note-----

In the first test case, there are only two choices: either $a =$ f and $b = $ c or $a = $ c and $b = $ f. And $a = $c is lexicographically smaller than $a = $ f.

In the second test case, a is the only character in the string.

In the third test case, it can be proven that b is the lexicographically smallest subsequence of $s$. The second string can be of two variants; one of them is given here.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
def read_nums():
	return [int(x) for x in input().split()]

def solve():
	s = input()
	a = min(s)
	i = s.index(a)
	b = s[:i] + s[i + 1:]
	print(a, b)

def main():
	(t,) = read_nums()
	for _ in range(t):
		solve()
main()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp_vars_int = lambda : map(int, input().split())
inp_list_int = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
	s = input()
	a = min(s)
	b = s.replace(a, '', 1)
	print(a, b)


for _ in range(int(input())):
	g = input()
	h = list(g)
	t = ''
	for i in range(97, 97 + 26):
		if g.count(chr(i)) != 0:
			t = chr(i)
			break
	h.remove(t)
	ans = ''.join(h)
	print(t, ans)


t = int(input())
for _ in range(t):
	s = input()
	a = min(s)
	for i in range(len(s)):
		if s[i] == a:
			print(a, s[:i] + s[i + 1:])
			break


t = int(input())
for i in range(t):
	s = input()
	mn = s[0]
	ind = 0
	for j in range(1, len(s)):
		if s[j] < mn:
			mn = s[j]
			ind = j
	print(mn, s[:ind] + s[ind + 1:])


def min_alha(s):
	mi = s[0]
	for x in s:
		if x < mi:
			mi = x
	return mi
n = int(input())
ans = list()
for i in range(n):
	s = input()
	x = min_alha(s)
	for j in range(len(s)):
		if s[j] == x:
			s = s[:j] + s[j + 1:]
			break
	ans.append((x, s))
for x in ans:
	print(x[0], x[1])


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = list(input().rstrip())
	idx = 0
	MIN = ord(s[0])
	for i in range(1, len(s)):
		if ord(s[i]) < MIN:
			idx = i
			MIN = ord(s[i])
	print(s[idx], ''.join(s[:idx] + s[idx + 1:]))


import sys
input = sys.stdin.readline

def get_integers():
	return map(int, input().strip().split())
t = int(input().strip())
for _ in range(t):
	s = input().strip()
	mn = ord('z')
	idx = 0
	for (i, char) in enumerate(s):
		if ord(char) < mn:
			mn = ord(char)
			idx = i
	print(s[idx], s[:idx] + s[idx + 1:])


t = int(input())
while t > 0:
	s = input()
	print(min(s), end=' ')
	ind = list(s).index(min(s))
	print(s[:ind] + s[ind + 1:])
	t -= 1


n = int(input())
a = []
for i in range(n):
	arr = list(input())
	b = min(arr)
	arr.remove(b)
	a.append((b, ''.join(arr)))
for i in range(n):
	print(a[i][0], a[i][1])


n = int(input())
res = []
for _ in range(n):
	s = list(input())
	s1 = sorted(s)
	a = s1[0]
	s.remove(a)
	res.append(a + ' ' + ''.join(s))
for i in res:
	print(i)


from sys import stdin

def solve():
	for _ in range(int(stdin.readline().strip())):
		S = list(stdin.readline().rstrip())
		x = min(S)
		y = ''
		f = 0
		for c in S:
			if c == x and (not f):
				f = 1
				continue
			y += c
		print(x, y)
solve()


t = int(input())
for i in range(t):
	s = input()
	minim = min(s)
	found = s.find(minim)
	print(minim, s[0:found] + s[found + 1:])


t = int(input())
while t:
	t -= 1
	k = input()
	mn = min(k)
	k = k.replace(mn, '', 1)
	print(mn, k)


for i in range(int(input())):
	S = input()
	a = min(S)
	c = S.index(a)
	if c != len(S) - 1 and c != 0:
		b = S[0:c] + S[c + 1:]
	elif c == 0:
		b = S[1:]
	else:
		b = S[0:len(S) - 1]
	print(a, b)


t = int(input())
while t != 0:
	s = input()
	lst = [i for i in s]
	lst.sort()
	a = lst[0]
	s = s.replace(a, '', 1)
	print(a, s)
	t = t - 1


for __ in range(int(input())):
	S = input()
	SS = sorted(list(S))
	print(SS[0], S.replace(SS[0], '', 1))


for case in range(int(input())):
	s = input()
	x = min(s)
	s = s.replace(x, '', 1)
	print(x + ' ' + s)


t = int(input())
for _ in range(t):
	s = list(input())
	a = min(list(set(s)))
	del s[s.index(a)]
	print(f"{a} {''.join(s)}")


alpha = 'abcdefghijklmnopqrstuvwxyz'
loop = int(input())
for x in range(0, loop):
	word = input()
	for x in alpha:
		if x in word:
			word = word.replace(x, '', 1)
			word = f'{x} {word}'
			print(word)
			break


for i in range(int(input())):
	s = input()
	min_ = min(s)
	s = s.replace(min_, '', 1)
	print(min_, s)


def solve(s):
	min = s[0]
	c = 0
	for i in range(len(s)):
		if s[i] < min:
			min = s[i]
			c = i
	print(min + ' ', end='')
	print(s[:c] + s[c + 1:])
t = int(input())
for _ in range(t):
	s = input()
	solve(s)


for _ in range(int(input())):
	s = list(input())
	m = min(s)
	s.pop(s.index(m))
	print(m, ''.join(s))


n = int(input())
for x in range(n):
	x = input()
	a = min(x)
	b = x.index(a)
	x = list(x)
	x.pop(b)
	print(a, ''.join(x))


import sys
inp = sys.stdin.readline

def solve():
	s = inp().strip()
	for i in range(26):
		a = chr(ord('a') + i)
		if a in s:
			f = s.find(a)
			b = s[:f] + s[f + 1:]
			print(a, b)
			return

def main():
	for i in range(int(inp())):
		solve()
main()


x = int(input())
for i in range(x):
	s = list(input())
	y = sorted(s)[0]
	s.remove(y)
	print(y, ' ', ''.join(s))


for _ in range(int(input())):
	s = input()
	r = ''.join(sorted(s))
	s = s.replace(r[0], '', 1)
	print(r[0], s)


for _ in range(int(input())):
	s = input()
	r1 = min(s)
	for i in range(len(s)):
		if s[i] == r1:
			r2 = s[0:i] + s[i + 1:len(s)]
			break
	print(r1 + ' ' + r2)


for _ in range(int(input())):
	s = input()
	k = list(s)
	p = k.copy()
	p.sort()
	print(p[0], end=' ')
	k.remove(p[0])
	print(''.join(k))


t = int(input())
for _ in range(t):
	s = input()
	a = s[0]
	for i in s:
		if i < a:
			a = i
	b = s.replace(a, '', 1)
	print(a, b)


for _ in range(int(input())):
	s = input()
	x = min(s)
	s = s.replace(x, '', 1)
	print(x, s)


for _ in range(int(input())):
	s = input()
	idx = s.index(min(s))
	print(min(s), s[:idx] + s[idx + 1:])


for i in range(int(input())):
	n = input()
	s = min(n)
	n = n.replace(s, '', 1)
	print(s, n)


for _ in range(0, int(input())):
	s = input()
	a = min(s)
	print(a, s.replace(a, '', 1))


for i in range(int(input())):
	s = input()
	r = min(s)
	print(r, s.replace(r, '', 1))


import math
t = int(input())
while t > 0:
	t -= 1
	s = input()
	ch = s[0]
	index = 0
	for i in range(1, len(s)):
		if s[i] < ch:
			ch = s[i]
			index = i
	print(ch, s[:index] + s[index + 1:])


x = input()
x = int(x)
sent = []
for i in range(x):
	y = input()
	sent.append(y)
for sub in sent:
	a = sorted(sub)[0]
	idx = sub.find(a)
	b = sub.replace(a, '', 1)
	print(a, ' ', b)


for _ in range(int(input())):
	a = list(input())
	m = min(a)
	a.remove(m)
	print(m, ''.join(a))


for _ in range(int(input())):
	n1 = input()
	minval = min(n1)
	print(minval, n1.replace(minval, '', 1))


import sys
for _ in range(int(sys.stdin.readline().strip())):
	n1 = sys.stdin.readline().strip()
	minval = min(n1)
	print(minval, n1.replace(minval, '', 1))


t = int(input())
for _ in range(t):
	s = input()
	a = min(s)
	i = s.index(a)
	print(a, s[:i] + s[i + 1:])


for _ in range(int(input())):
	ch = input()
	x = min(ch)
	print(x, ch.replace(x, '', 1))


T = int(input())
for t in range(T):
	a = list(input())
	b = a[:]
	b.sort()
	a.remove(b[0])
	print(b[0], end=' ')
	print(''.join(a))


t = int(input())
for i in range(t):
	s = input()
	a = min(s)
	sci = s.find(a)
	b = s[:sci] + s[sci + 1:]
	print(a, b)


t = int(input())
for i in range(t):
	a = list(input())
	k = min(a)
	a.remove(k)
	print(k, ''.join(a))


import sys
num = int(input())
all = []
alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
while num:
	temp = input()
	all.append(temp)
	num -= 1
for item in all:
	for a in alpha:
		if a in item:
			sys.stdout.write(a)
			sys.stdout.write(' ')
			sys.stdout.write(item.replace(a, '', 1))
			sys.stdout.write('\n')
			break


t = int(input())
while t > 0:
	t -= 1
	s = input()
	a = min(s)
	i = 0
	while s[i] != a:
		i += 1
	print(a, ' ', s[:i] + s[i + 1:len(s)])


for _ in range(int(input())):
	a = input()
	b = list(a)
	b.sort()
	print(b[0], a.replace(b[0], '', 1))


t = int(input())
for i in range(t):
	s = input()
	a = min(s)
	v = s.find(a)
	v = s[:v] + s[v + 1:]
	print(a, v)


for t in range(int(input())):
	s = input()
	mn = 0
	for i in set(s):
		if mn == 0:
			mn = i
		elif i < mn:
			mn = i
	print(mn, s.replace(mn, '', 1))


for _ in range(int(input())):
	s = input()
	j = s.index(min(s))
	print(s[j], s[:j] + s[j + 1:])


t = int(input())
for i in range(t):
	s = input()
	lis = list(s)
	a = min(lis)
	lis.remove(a)
	j = ''.join(lis)
	print(a, j)


for i in range(int(input())):
	string = input()
	letter = sorted(string)[0]
	print(letter, string.replace(letter, '', 1))


n = int(input())
S = []
for i in range(0, n):
	S.append(input())
for i in range(0, int(n)):
	A = sorted(S[i])
	S[i] = list(S[i])
	S[i].remove(A[0])
	print(A[0], ''.join(S[i]))


T = int(input())
for t in range(T):
	s = input()
	a = min(s)
	b = s.replace(a, '', 1)
	print(a, b)


for i in range(int(input())):
	n = input()
	li = list(n)
	min_value = list(min(li))
	li.remove(''.join(min_value))
	print(''.join(min_value), ''.join(li))


t = int(input())
for i in range(t):
	s = input()
	men = min(s)
	s1 = s.split(men, 1)
	res = ''.join(s1)
	print(men, res)


from sys import stdin
for _ in range(int(stdin.readline())):
	s = stdin.readline().strip()
	_min = min(s)
	a = s.index(_min)
	print(s[a], s[:a] + s[a + 1:])


for _ in range(int(input())):
	s = input()
	a = sorted(s)[0]
	b = s[:s.index(a)] + s[s.index(a) + 1:]
	print(a, b)


for i in [0] * int(input()):
	x = input()
	max = x[0]
	intmax = 0
	max = min(x)
	j = x.find(min(x))
	print(x[j] + ' ' + x[0:j] + x[j + 1:])


def check(x):
	p = list(x)
	p.sort()
	s = p[0]
	p.pop(0)
	p = list(x)
	p.remove(s)
	m = s + ' ' + ''.join(p)
	return m
c = int(input())
m = []
o = []
for j in range(c):
	s = input()
	o.append(s)
for i in o:
	t = check(i)
	m.append(t)
for f in m:
	print(f)


for _ in range(int(input())):
	s = str(input())
	m = min(s)
	n = s.replace(m, '', 1)
	print(m, n)


t = int(input())
arr = []
for i in range(t):
	s = input()
	m = 'z'
	for j in s:
		if ord(j) < ord(m):
			m = j
	index = s.index(m)
	s = s[:index] + s[index + 1:]
	arr.append(m + ' ' + s)
for i in arr:
	print(i)


def solve(n):
	m = min(n)
	result = n.replace(m, '', 1)
	print(m, result)
for _ in range(int(input())):
	n = input()
	solve(n)


while 1:
	n = int(input())
	if n in range(1, 1001):
		break
L = []
for i in range(n):
	while 1:
		s = input()
		if len(s) in range(2, 101):
			L.append(s)
			break
for s in L:
	a = min(s)
	b = s[:s.index(a)] + s[s.index(a) + 1:]
	print('{} {}'.format(a, b))


t = int(input())
for _ in range(t):
	s = input()
	min1 = min(s)
	print(min1, s.replace(min1, '', 1))


t = int(input())
for i in range(t):
	s = input()
	l = list(s)
	p = sorted(l)
	a = p[0]
	l.remove(a)
	b = ''.join(l)
	print(a, b)


for i in range(int(input())):
	data = input()
	data = list(data)
	print(min(data), end=' ')
	data.remove(min(data))
	b = ''.join(data)
	print(b)


t = int(input())
for _ in range(t):
	s = input()
	a = [i for i in s]
	print(min(a), end=' ')
	a.remove(min(a))
	print(''.join(a))


t = int(input())
cases = []
for i in range(t):
	s = input()
	cases.append(s)
for c in cases:
	k = c.find(min(c))
	print(c[k], c[0:k] + c[k + 1:])


t = int(input())
for i in range(t):
	s = list(input())
	x = sorted(s)
	a = x[0]
	s.remove(x[0])
	print(a, ''.join(s))


s = int(input())
for i in range(s):
	a = input()
	d = list(a)
	b = sorted(a)
	c = b[0]
	d.remove(c)
	print(c, ''.join(d))


for _ in range(int(input())):
	s = input()
	m = min(s)
	i = s.index(m)
	print(m, s[:i] + s[i + 1:])


class Solution:

	def ans(self, s: str) -> None:
		a = min(list(s))
		another = ''
		c = 0
		for i in range(len(s)):
			if s[i] == a:
				c = i
				break
		print(a, s[0:c] + s[c + 1:])
t = int(input())
for _ in range(t):
	s: str = input()
	obj = Solution()
	obj.ans(s)


for _ in [0] * int(input()):
	s = list(input())
	k = min(s)
	s.remove(k)
	print(k, ''.join(s))


import sys
input = sys.stdin.readline

def solve():
	s = input().strip()
	n = len(s)
	curr = s[0]
	idx = 0
	for i in range(n):
		if curr > s[i]:
			curr = s[i]
			idx = i
	return (curr, s[:idx] + s[idx + 1:])
for _ in range(int(input())):
	print(*solve())