You are given a string $s$, consisting of lowercase Latin letters. Every letter appears in it no more than twice.

Your task is to rearrange the letters in the string in such a way that for each pair of letters that appear exactly twice, the distance between the letters in the pair is the same. You are not allowed to add or remove letters.

It can be shown that the answer always exists. If there are multiple answers, print any of them.


-----Input-----

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

Each testcase consists of a non-empty string $s$, consisting of lowercase Latin letters. Every letter appears in the string no more than twice. The length of the string doesn't exceed $52$.


-----Output-----

For each testcase, print a single string. Every letter should appear in it the same number of times as it appears in string $s$. For each pair of letters that appear exactly twice, the distance between the letters in the pair should be the same.

If there are multiple answers, print any of them.


-----Examples-----

Input
3
oelhl
abcdcba
ac
Output
hello
ababcdc
ac


-----Note-----

In the first testcase of the example, the only letter that appears exactly twice is letter 'l'. You can rearrange the letters arbitrarily, since there are no distances to compare.

In the second testcase of the example, the letters that appear exactly twice are 'a', 'b' and 'c'. Initially, letters 'a' are distance $6$ apart, letters 'b' are distance $4$ apart and letters 'c' are distance $2$ apart. They are not the same, so we have to rearrange the letters. After rearrangement, letters 'a' are distance $2$ apart, letters 'b' are distance $2$ apart and letters 'c' are distance $2$ apart. They are all the same, so the answer is valid.

In the third testcase of the example, there are no letters that appear exactly twice. Thus, any rearrangement is valid. Including not changing the string at all.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Constructive algorithms


Solutions:
n_test = int(input())
for i in range(n_test):
	s = input()
	print(''.join(sorted(s)))


a = []
for i in range(int(input())):
	s = input()
	ns = ''
	s1 = sorted(s)
	for j in s1:
		ns = ns + j
	a.append(ns)
for i in a:
	print(i)


for _ in range(int(input())):
	print(''.join(sorted(input())))


def main(s):
	s = [i for i in s]
	s.sort()
	s = ''.join(s)
	return s
t = int(input())
ans = []
for i in range(t):
	s = input()
	ans.append(main(s))
for e in ans:
	print(e)


t = int(input())
for i in range(t):
	l = []
	s = input()
	l[:0] = s
	l.sort()
	print(''.join(l))


for _ in range(int(input())):
	x = list(map(str, input().strip()))
	y = sorted(x)
	print(''.join(y))


for i in range(int(input())):
	s = input()
	res = ''.join(sorted(s))
	print(res)


t = int(input())
for i in range(t):
	s = input()
	print(''.join(sorted(s)))


for i in range(int(input())):
	s = str(input())
	print(''.join(sorted(s)))


t = int(input())
while t > 0:
	s = str(input())
	s = sorted(s)
	print(''.join(s))
	t -= 1


t = int(input())
for i in range(t):
	x = list(input())
	x.sort()
	y = ''.join(x)
	print(y)


t = int(input())
while t:
	s = input()
	s_ordenado = sorted(s)
	t = t - 1
	print(''.join(s_ordenado))


def main():
	t = int(input())
	res = [None] * t
	for i in range(t):
		inp = str(input())
		res[i] = ''.join(sorted(inp))
	print(*res, sep='\n')
main()


answers = []
for i in range(int(input())):
	ans = ''.join(sorted(list(input())))
	answers.append(ans)
for i in answers:
	print(i)


def letters():
	n = int(input())
	for _ in range(n):
		line = input()
		print(''.join(sorted(line)))
letters()


for _ in range(int(input())):
	s = str(input())
	print(''.join(sorted(s)))


tests = int(input())
for _ in range(tests):
	s = list(input())
	s.sort()
	print(''.join(s))


n = int(input())
for i in range(n):
	w = list(input())
	w.sort()
	print(''.join(w))


def listToString(s):
	str1 = ''
	for ele in s:
		str1 += ele
	return str1
i = int(input())
c = ''
for j in range(i):
	a = input()
	a = list(a)
	a = sorted(a)
	a = listToString(a)
	print(a)


n = int(input())
for i in range(n):
	string = [*input()]
	print(''.join(sorted(string)))


import sys, math
sys.setrecursionlimit(10 ** 7)
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = input()
	s = list(n)
	s.sort()
	ans = ''.join(s)
	print(ans)


ans = []
for _ in range(int(input())):
	s = [i for i in input()]
	s.sort()
	ans.append(''.join(s))
for i in ans:
	print(i)


from collections import Counter
T = int(input())
for _ in range(T):
	s = input()
	print(''.join(sorted(s)))


import math
for _ in range(int(input())):
	s = input()
	x = ''
	for i in sorted(s):
		x += i
	print(x)


import sys
n = int(sys.stdin.readline())
for _ in range(n):
	s = sys.stdin.readline().rstrip()
	print(''.join(sorted(s)))


def funct(word):
	return ''.join(sorted(word))
for _ in range(int(input())):
	print(funct(input()))


t = int(input())
ans = []
for _ in range(t):
	letters = list(input())
	letters = sorted(letters)
	res = ''.join(letters)
	ans.append(res)
for res in ans:
	print(res)


t = int(input())
for _ in range(t):
	s = str(input())
	print(''.join(list(sorted(s))))


N = int(input())
for i in range(N):
	s = input()
	arr = []
	for i in s:
		arr.append(i)
	arr.sort()
	print(''.join(arr))


t = int(input())
ans = []
while t > 0:
	t -= 1
	s = input()
	s = sorted(s)
	ans.append(''.join(s))
print('\n'.join(ans))


print(*(''.join(sorted(input())) for _ in range(int(input()))), sep='\n')


for _ in range(int(input())):
	s = input()
	s = sorted(s)
	a = ''
	for i in s:
		a += i
	print(a)


t = int(input())
while t > 0:
	print(''.join(sorted(list(input()))))
	t = t - 1


t = int(input())
for _ in range(t):
	s = list(input())
	s.sort()
	print(''.join(s))


n = int(input())
for i in range(n):
	a = input()
	print(''.join(sorted(a)))


t = int(input())
Satr = []
for i in range(t):
	s = input()
	s = ''.join(sorted(s))
	Satr.append(s)
for i in range(t):
	print(Satr[i])


for i in range(int(input())):
	print(''.join(sorted(input())))


def equiLetters(s):
	return ''.join(sorted(s))
T = int(input())
for i in range(T):
	print(equiLetters(input()))


tests = int(input())
for test in range(tests):
	s = [x for x in input()]
	s.sort()
	print(''.join(s))


mod = 10000000
for _ in range(int(input())):
	s = list(input())
	s = sorted(s)
	print(''.join(s))


t = int(input())
for tt in range(t):
	a = input()
	aa = [r for r in a]
	aa.sort()
	print(''.join(aa))