You are given a huge integer $a$ consisting of $n$ digits ($n$ is between $1$ and $3 \cdot 10^5$, inclusive). It may contain leading zeros.

You can swap two digits on adjacent (neighboring) positions if the swapping digits are of different parity (that is, they have different remainders when divided by $2$). 

For example, if $a = 032867235$ you can get the following integers in a single operation:   $302867235$ if you swap the first and the second digits;  $023867235$ if you swap the second and the third digits;  $032876235$ if you swap the fifth and the sixth digits;  $032862735$ if you swap the sixth and the seventh digits;  $032867325$ if you swap the seventh and the eighth digits. 

Note, that you can't swap digits on positions $2$ and $4$ because the positions are not adjacent. Also, you can't swap digits on positions $3$ and $4$ because the digits have the same parity.

You can perform any number (possibly, zero) of such operations.

Find the minimum integer you can obtain.

Note that the resulting integer also may contain leading zeros.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input.

The only line of each test case contains the integer $a$, its length $n$ is between $1$ and $3 \cdot 10^5$, inclusive.

It is guaranteed that the sum of all values $n$ does not exceed $3 \cdot 10^5$.


-----Output-----

For each test case print line — the minimum integer you can obtain.


-----Example-----
Input
3
0709
1337
246432

Output
0079
1337
234642



-----Note-----

In the first test case, you can perform the following sequence of operations (the pair of swapped digits is highlighted): $0 \underline{\textbf{70}} 9 \rightarrow 0079$.

In the second test case, the initial integer is optimal. 

In the third test case you can perform the following sequence of operations: $246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 234642$.

Difficulty: interview

Starter code:

Solutions:
for __ in range(int(input())):
    a = list(map(int, input()))
    ar1 = []
    ar2 = []
    for elem in a:
        if elem % 2 == 0:
            ar1.append(elem)
        else:
            ar2.append(elem)
    ans = []
    i = 0
    j = 0
    while i < len(ar1) and j < len(ar2):
        if ar1[i] < ar2[j]:
            ans.append(ar1[i])
            i += 1
        else:
            ans.append(ar2[j])
            j += 1
    if i < len(ar1):
        for h in range(i, len(ar1)):
            ans.append(ar1[h])
    if j < len(ar2):
        for h in range(j, len(ar2)):
            ans.append(ar2[h])
    print(''.join(map(str, ans)))

# PARITY'S RELATIVE POSITION DOESN'T CHANGE! (PROBLEM C)
def solve(s):
    # return list
    evens = [u for u in s if u % 2 == 0]
    odds  = [u for u in s if u % 2 == 1]
    if len(odds) == 0:
        return evens
    ans = []
    inserted_odd = 0
    current_odd = odds[inserted_odd]
    for i in range(len(evens)):
        while current_odd < evens[i] and inserted_odd < len(odds):
            ans.append(current_odd)
            inserted_odd += 1
            if inserted_odd < len(odds):
                current_odd = odds[inserted_odd]
        ans.append(evens[i])
    while inserted_odd < len(odds):
        ans.append(current_odd)
        inserted_odd += 1
        if inserted_odd < len(odds):
            current_odd = odds[inserted_odd]
    return ans


for _ in range(int(input())):
    s = list(map(int, list(input())))
    ans = solve(s)
    print (''.join(map(str, ans)))

for t in range(int(input())):
      s=input()
      l=len(s)
      eve=""
      odd=""
      for i in range(l):
            if((ord(s[i])-ord("0"))%2 == 0):
                  eve+=s[i]
            else:
                  odd+=s[i]
      e0=len(eve)
      o0=len(odd)
      e=0
      o=0
      a=""
      for i in range(l):
            if(o == o0):
                  a+=eve[e]
                  e+=1
            elif(e==e0):
                  a+=odd[o]
                  o+=1
            elif(ord(eve[e])>ord(odd[o])):
                  a+=odd[o]
                  o+=1
            else:
                  a+=eve[e]
                  e+=1
      print(a)


import sys
input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T):
    A = [int(a) for a in input()]
    N = len(A)
    O = []
    E = []
    for i in range(N):
        if A[i] % 2:
            O.append(A[i])
        else:
            E.append(A[i])
    O = O[::-1]
    E = E[::-1]
    B = []
    while O or E:
        if not O:
            B.append(E.pop())
        elif not E:
            B.append(O.pop())
        elif O[-1] < E[-1]:
            B.append(O.pop())
        else:
            B.append(E.pop())
    print("".join(map(str, B)))



import sys
def I():
    return sys.stdin.readline().rstrip()

for _ in range( int( I( ) ) ):
    e, o, a = [], [], []
    for c in I():
        x = ord( c ) - ord( '0' )
        if x & 1:
            o.append( x )
        else:
            e.append( x )
    i, j = 0, 0
    while i < len( o ) or j < len( e ):
        if i < len( o ) and j < len( e ):
            if o[ i ] < e[ j ]:
                a.append( chr(o[ i ] + ord( '0' )))
                i += 1
            else:
                a.append( chr(e[ j ] + ord( '0' )))
                j += 1
        elif i < len( o ):
            a.append( chr(o[ i ] + ord( '0' )))
            i += 1
        else:
            a.append( chr(e[ j ] + ord( '0' )))
            j += 1
    print( "".join( a ) )



from itertools import groupby
for _ in range(int(input())):
    s = input()
    n = len(s)
    i = j = 0
    while i < n or j < n:
        while i < n and int(s[i]) % 2:
            i += 1
        while j < n and not int(s[j]) % 2:
            j += 1
        if i == j == n:
            break
        if i < n and (j == n or s[i] < s[j]):
            print(end=s[i])
            i += 1
        else:
            print(end=s[j])
            j += 1
    print()


# PARITY'S RELATIVE POSITION DOESN'T CHANGE! (PROBLEM C)
def solve1(s):
    # return list
    evens = [u for u in s if u % 2 == 0]
    odds  = [u for u in s if u % 2 == 1]
    if len(odds) == 0:
        return evens
    ans = []
    inserted_odd = 0
    current_odd = odds[inserted_odd]
    for i in range(len(evens)):
        while current_odd < evens[i] and inserted_odd < len(odds):
            ans.append(current_odd)
            inserted_odd += 1
            if inserted_odd < len(odds):
                current_odd = odds[inserted_odd]
        ans.append(evens[i])
    while inserted_odd < len(odds):
        ans.append(current_odd)
        inserted_odd += 1
        if inserted_odd < len(odds):
            current_odd = odds[inserted_odd]
    return ans

def solve2(s):
    # return list
    # lazy code lmao
    odds = [u for u in s if u % 2 == 0]
    evens  = [u for u in s if u % 2 == 1]
    if len(odds) == 0:
        return evens
    ans = []
    inserted_odd = 0
    current_odd = odds[inserted_odd]
    for i in range(len(evens)):
        while current_odd < evens[i] and inserted_odd < len(odds):
            ans.append(current_odd)
            inserted_odd += 1
            if inserted_odd < len(odds):
                current_odd = odds[inserted_odd]
        ans.append(evens[i])
    while inserted_odd < len(odds):
        ans.append(current_odd)
        inserted_odd += 1
        if inserted_odd < len(odds):
            current_odd = odds[inserted_odd]
    return ans

for _ in range(int(input())):
    s = list(map(int, list(input())))
    ans = min(solve1(s), solve2(s))
    print (''.join(map(str, ans)))

import sys
input = sys.stdin.readline

t=int(input())

ESET={"0","2","4","6","8"}

from collections import deque

for test in range(t):

    n=input().strip()

    E=deque()
    O=deque()

    for s in n:
        if s in ESET:
            E.append(s)
        else:
            O.append(s)

    ANS=[]
    while E and O:
        if E[0]<O[0]:
            x=E.popleft()
            ANS.append(x)
        else:
            x=O.popleft()
            ANS.append(x)

    #print(ANS,E,O)

    if len(E)!=0:
        ANS.extend(E)
    elif len(O)!=0:
        ANS.extend(O)

    print("".join(ANS))


import sys
from collections import deque
input = sys.stdin.readline


q = int(input())
s = [input() for i in range(q)]
for i in range(q):
    a0 = deque([])
    a1 = deque([])
    for j in range(len(s[i]) - 1):
        tmp = int(s[i][j])
        if tmp % 2 == 0:
            a0.append(tmp)
        else:
            a1.append(tmp)
    ans = []
    while True:
        if a0 and a1:
            if a0[0] > a1[0]:
                tmp = a1.popleft()
                ans.append(tmp)
            else:
                tmp = a0.popleft()
                ans.append(tmp)
        else:
            while a0:
                tmp = a0.popleft()
                ans.append(tmp)
            while a1:
                tmp = a1.popleft()
                ans.append(tmp)
            break
    print("".join(map(str, ans)))


t = int(input())
for _ in range(t):
    ev = []
    od = []
    s = map(int,list(input()))
    for v in s:
        if v % 2:
            od.append(v)
        else:
            ev.append(v)
    ev.append(1000)
    od.append(1000)
    ep = 0
    op = 0
    while ep < len(ev)-1 or op < len(od)-1:
        if ev[ep] < od[op]:
            print(ev[ep],end='')
            ep += 1
        else:
            print(od[op],end='')
            op += 1
    print("")


for _ in range(int(input())):
    a = list(input())
    odd = []
    even = []
    for elem in a:
        elem = int(elem)
        if elem % 2 == 0:
            even.append(elem)
        else:
            odd.append(elem)
    i = 0
    j = 0
    output = []
    for _ in range(len(a)):
        if i == len(odd):
            output.append(str(even[j]))
            j += 1
        elif j == len(even):
            output.append(str(odd[i]))
            i += 1
        else:
            if odd[i] < even[j]:
                output.append(str(odd[i]))
                i += 1
            else:
                output.append(str(even[j]))
                j += 1
    print("".join(output))


'''
Created on 2019. 9. 21.

@author: kkhh88
'''
#q = int(input())
#x, y = map(int,input().split(' '))

q = int(input())
for _ in range(q):
    s0 = ''
    s1 = ''
    s = input()
    ans = ''
    for c in s:
        if ord(c) % 2 == 1:
            s1 = s1 + c
        else:
            s0 = s0 + c
    
    l0 = 0
    l1 = 0
    while len(s0) > l0 and len(s1) > l1:
        if s0[l0] > s1[l1]:
            ans = ans + s1[l1]
            l1 = l1 + 1
        else:
            ans = ans + s0[l0]
            l0 = l0 + 1
    print (ans + s1[l1:] + s0[l0:])

n = int(input())
for ewfe in range(n):
	s = input()
	par = []
	npar = []
	for i in s:
		if int(i) % 2 == 0:
			par.append(int(i))
		else:
			npar.append(int(i))
	pa = 0
	npa = 0
	odp = []
	while True:
		if pa == len(par) and npa == len(npar):
			break
		if pa <= len(par) - 1 and npa <= len(npar) -1:
			if par[pa] < npar[npa]:
				odp.append(par[pa])
				pa += 1
			else:
				odp.append(npar[npa])
				npa += 1
		else:
			if pa == len(par):
				odp.append(npar[npa])
				npa += 1
			else:
				odp.append(par[pa])
				pa += 1
	k = len(odp)
	for i in range(k):
		if i < k - 1:
			print(odp[i], end = "")
		else:
			print(odp[i])

for _ in range(int(input())):
    s = input()
    e = []
    o = []
    for i in s:
        if int(i)%2:
            o.append(int(i))
        else:
            e.append(int(i))
    o.reverse()
    e.reverse()
    ans = []
    while e and o:
        if e[-1] < o[-1]:
            ans.append(e.pop())
        else:
            ans.append(o.pop())
    if e:
        while e:
            ans.append(e.pop())
    else:
        while o:
            ans.append(o.pop())
    print(''.join(map(str, ans)))

Q = int(input())
for q in range(Q):
    s = input()

    chet = []
    nechet = []
    for i in s:
        if int(i) % 2 == 0:
            chet.append(int(i))
        else:
            nechet.append(int(i))
    #chet.sort()
    #nechet.sort()
    chet.append(10)
    nechet.append(10)

    i = 0
    j = 0
    ans = []
    while i < len(chet) and j < len(nechet):
        if i == len(chet) - 1 and j == len(nechet) - 1:
            break
        if chet[i] < nechet[j]:
            ans.append(chet[i])
            i += 1
        else:
            ans.append(nechet[j])
            j += 1

    print(*ans, sep='')


t = int(input())
for j in range(t):
    s = input()
    first = []
    second = []
    for i in range(len(s)):
        if int(s[i]) % 2:
            first.append(int(s[i]))
        else:
            second.append(int(s[i]))
    i_f = 0
    i_s = 0
    while i_f < len(first) and i_s < len(second):
        if first[i_f] < second[i_s]:
            print(first[i_f], end = '')
            i_f += 1
        else:
            print(second[i_s], end = '')
            i_s += 1
    while i_f < len(first):
        print(first[i_f], end = '')
        i_f += 1
    while i_s < len(second):
        print(second[i_s], end = '')
        i_s += 1
    print()


import sys
readline = sys.stdin.readline
T = int(readline())
Ans = [None]*T

for qu in range(T):
    S = list(map(ord, readline().strip()))
    
    SE = []
    SO = []
    
    for s in S:
        if s % 2 == 0:
            SE.append(s)
        else:
            SO.append(s)
    
    LE = len(SE)
    LO = len(SO)
    inf = 10000
    SE.append(inf)
    SO.append(inf)
    cnte = 0
    cnto = 0
    ans = []
    for _ in range(LE + LO):
        if SE[cnte] < SO[cnto]:
            ans.append(SE[cnte])
            cnte += 1
        else:
            ans.append(SO[cnto])
            cnto += 1
    
    Ans[qu] = ans

for a in Ans:
    sys.stdout.write(''.join(map(chr, a)))
    sys.stdout.write('\n')


from collections import deque
for _ in range(int(input())):
    x = input()
    even = deque()
    odd = deque()

    for i in map(int, x):
        if i % 2 == 0:
            even.append(i)
        else:
            odd.append(i)
    #print(even, odd)
    ans = deque()
    while len(ans)<len(x):
        if len(even)==0:
            ans.append(odd.popleft())
        elif len(odd) == 0:
            ans.append(even.popleft())
        elif even[0] < odd[0]:
            ans.append(even.popleft())
        else:
            ans.append(odd.popleft())
    print(''.join(str(i) for i in ans))

mans = ""
for _ in range(int(input())):
    s=input()
    ev=''
    od=''
    for x in s:
    	if x in '13579':
    		od+=x
    	else:
    		ev+=x
    ans=''
    uv=0
    ud=0
    while uv < len(ev) or ud < len(od):
    	if uv == len(ev):
    		ans+=od[ud]
    		ud+=1
    	elif ud == len(od):
    		ans+=ev[uv]
    		uv+=1
    	elif ev[uv]<od[ud]:
    		ans+=ev[uv]
    		uv+=1
    	else:
    		ans+=od[ud];ud+=1
    mans += ans
    mans += '\n'
print(mans)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))

def solve():
    nums = [int(i) for i in input().strip()]
    odds = []
    evens = []
    lodd, leven = 0, 0
    for num in nums:
        if num % 2 == 1:
            odds.append(num)
            lodd += 1
        else:
            evens.append(num)
            leven += 1

    # lodd = len(odds)
    # leven = len(evens)
    odds.append(100)
    evens.append(100)
    io, ie = 0, 0
    ans = []
    while(True):
        if odds[io] < evens[ie]:
            ans.append(odds[io])
            io += 1
            if io == lodd:
                ans += evens[ie:leven]
                break
        else:
            ans.append(evens[ie])
            ie += 1
            if ie == leven:
                ans += odds[io:lodd]
                break
        # if io == lodd and ie == leven:
        #     break
    # nums.reverse()

    print("".join(list(map(str, ans))))

    return

def main():
    t = getN()
    for times in range(t):
        solve()


def __starting_point():
    main()
__starting_point()

from collections import deque
t = int(input())
for i in range(t):
    n = list(map(int, input()))
    chet, nechet = deque(), deque()
    for el in n:
        if el % 2 == 0:
            chet.append(el)
        else:
            nechet.append(el)
    ans = []
    while chet or nechet:
        if chet and nechet:
            if chet[0] < nechet[0]:
                ans.append(chet.popleft())
            else:
                ans.append(nechet.popleft())
        elif chet:
            ans.append(chet.popleft())
        else:
            ans.append(nechet.popleft())
    print(''.join(map(str, ans)))

for _ in range(int(input())):
    long = list(map(int, list(input())))
    odd = []
    even = []
    for n in long:
        if n % 2 == 1:
            odd.append(n)
        else:
            even.append(n)
    even.append(10)
    odd.append(11)
    i1 = 0
    i2 = 0
    for i in range(len(long)):
        if even[i1] < odd[i2]:
            print(even[i1], end="")
            i1 += 1
        else:
            print(odd[i2], end="")
            i2 += 1
    print()


#!/usr/bin/env python3
import sys
INF = 10**9
sys.setrecursionlimit(10**8)
# input = sys.stdin.buffer.readline

n = int(input())
for i in range(n):
    s = input().rstrip()
    odds = []
    evens = [] 
    for ch in s:
        if int(ch) % 2 == 0:
            evens.append(int(ch))
        else:
            odds.append(int(ch))
    evens.append(INF)
    odds.append(INF)
    ans = []
    eid = 0
    oid = 0
    while evens[eid] != INF or odds[oid] != INF:
        if evens[eid] < odds[oid]:
            ans.append(evens[eid])
            eid += 1
        else:
            ans.append(odds[oid])
            oid += 1
    print("".join([str(item) for item in ans]))

q=int(input())
for t in range(q):
    s=input()
    ch=[]
    nch=[]
    for i in range(len(s)):
        if int(s[i])%2==0:
            ch.append(int(s[i]))
        else:
            nch.append(int(s[i]))
    ans=[]
    i1=0
    i2=0
    while i1<len(ch) and i2<len(nch):
        if ch[i1]<nch[i2]:
            ans.append(ch[i1])
            i1+=1
        else:
            ans.append(nch[i2])
            i2+=1
    while i2<len(nch):
        ans.append(nch[i2])
        i2+=1
    while i1 < len(ch):
        ans.append(ch[i1])
        i1+=1
    for i in range(len(ans)):
        print(ans[i],end='')
    print()

t = int(input())
for i in range(t):
    nums = list(map(int, list(input())))
    nums0, nums1 = [], []
    for num in nums:
        if num % 2 == 0:
            nums0.append(str(num))
        else:
            nums1.append(str(num))
    nums0.append(str(99))
    nums1.append(str(99))
    p0, p1 = 0, 0
    l0, l1 = len(nums0) - 1, len(nums1) - 1
    ans = str()
    while p0 < l0 or p1 < l1:
        p0_prev = p0
        while p0 < l0 and nums0[p0] < nums1[p1]:
            p0 += 1
        ans += ''.join(nums0[p0_prev: p0])
        p1_prev = p1
        while p1 < l1 and nums1[p1] < nums0[p0]:
            p1 += 1
        ans += ''.join(nums1[p1_prev: p1])
    print(ans)