Recently Polycarp noticed that some of the buttons of his keyboard are malfunctioning. For simplicity, we assume that Polycarp's keyboard contains $26$ buttons (one for each letter of the Latin alphabet). Each button is either working fine or malfunctioning. 

To check which buttons need replacement, Polycarp pressed some buttons in sequence, and a string $s$ appeared on the screen. When Polycarp presses a button with character $c$, one of the following events happened:

  if the button was working correctly, a character $c$ appeared at the end of the string Polycarp was typing;  if the button was malfunctioning, two characters $c$ appeared at the end of the string. 

For example, suppose the buttons corresponding to characters a and c are working correctly, and the button corresponding to b is malfunctioning. If Polycarp presses the buttons in the order a, b, a, c, a, b, a, then the string he is typing changes as follows: a $\rightarrow$ abb $\rightarrow$ abba $\rightarrow$ abbac $\rightarrow$ abbaca $\rightarrow$ abbacabb $\rightarrow$ abbacabba.

You are given a string $s$ which appeared on the screen after Polycarp pressed some buttons. Help Polycarp to determine which buttons are working correctly for sure (that is, this string could not appear on the screen if any of these buttons was malfunctioning).

You may assume that the buttons don't start malfunctioning when Polycarp types the string: each button either works correctly throughout the whole process, or malfunctions throughout the whole process.


-----Input-----

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

Then the test cases follow. Each test case is represented by one line containing a string $s$ consisting of no less than $1$ and no more than $500$ lowercase Latin letters.


-----Output-----

For each test case, print one line containing a string $res$. The string $res$ should contain all characters which correspond to buttons that work correctly in alphabetical order, without any separators or repetitions. If all buttons may malfunction, $res$ should be empty.


-----Example-----
Input
4
a
zzaaz
ccff
cbddbb

Output
a
z

bc

Difficulty: interview

Starter code:

Solutions:
n = int( input() )
for _ in range( n ):
    s = input()
    i = 0
    a = set()
    while i < len( s ):
        if i == len( s ) - 1 or s[ i ] != s[ i + 1 ]:
            a.add( s[ i ] )
            i += 1
        else:
            i += 2
    l = [ c for c in a ]
    l.sort()
    print( "".join( l ) )


for _ in range(int(input())):
    s = input()
    n = len(s)
    s += '$'
    i = 0
    ans = set()
    while i < n:
        c = s[i]
        if c != s[i + 1]:
            ans.add(c)
            i += 1
        else:
            i += 2
    print(''.join(sorted(ans)))


for _ in range(int(input())):
    s = input()
    ans = set()
    cnt = 1
    c = s[0]
    for c1 in s[1:]:
        if c1 != c:
            if cnt % 2 == 1:
                ans.add(c)
            cnt = 1
            c = c1
        else:
            cnt+=1
    if cnt % 2 == 1:
        ans.add(c)
    print(''.join(sorted(ans)))

for _ in range(int(input())):
    s = input()
    n = len(s)
    i = 0
    valid = set()
    while i < n:
        j = i + 1
        while j < n and s[j] == s[i]: j += 1
        if (j - i) & 1: valid.add(s[i])
        i = j
    print(''.join(sorted(valid)))

for i in range(int(input())):
    s = input()
    working = []
    j = 0
    while j < len(s):
        nextJ = j+1
        while nextJ < len(s) and s[nextJ] == s[j]:
            nextJ += 1
        if (nextJ - j) % 2 == 1:
            if s[j] not in working:
                working.append(s[j])
        j = nextJ
    working.sort()
    print("".join(working))


l=[]
for i in range(int(input())):
    x = input().upper()
    ly=""
    for i in range(65,91):
        ch = chr(i)
        if x.replace(ch+ch,"").find(ch) != -1:
            ly += ch.lower()
    l.append(ly)

print("\n".join(l))

t = int(input())

def run_length_compress(string):
    """文字列をランレングス圧縮する
    例) string = "aabccaaabb" -> [(2, a), (1, b), (2, c), (3, a), (2, b)]
    """
    string = string + "@" # string中に絶対に現れない文字を番兵とする
    n = len(string)

    begin = 0
    end = 1
    cnt = 1
    ans = []
    while True:
        if end >= n:
            break
        if string[begin] == string[end]:
            end += 1
            cnt += 1
        else:
            ans.append((cnt, string[begin]))
            begin = end
            end = begin + 1
            cnt = 1

    return ans

  
for _ in range(t):
    s = input()
    r = run_length_compress(s)
    memo = {}
    for i, char in r:
        if i %2 == 1:
            memo[char] = 1
    ans = []
    for i in memo:
        ans.append(i)
    ans = sorted(ans)
    print("".join(ans))

for _ in range(int(input())):
	s = input()
	t = ''
	lc=s[0]
	cnt=1
	for i in range(1,len(s)):
		if s[i]==lc:
			cnt+=1
		else:
			t+=lc*(cnt%2)
			lc=s[i]
			cnt=1
	t+=lc*(cnt%2)
	print(''.join(sorted(list(set(t)))))

TC = int(input())
for tc in range(TC):
	grps = []
	for c in input():
		if (not grps) or grps[-1][0] != c:
			grps.append([c, 1])
		else:
			grps[-1][1] += 1
	works = [False]*26
	for c, p in grps:
		if p % 2 == 1: works[ord(c)-ord('a')] = True
	res = ''.join(chr(x+ord('a')) for x in range(26) if works[x])
	print(res)
	


from itertools import groupby
t = int(input())
for _ in range(t):
    correct = set()
    for k, it in groupby(input()):
        if len(tuple(it)) % 2:
            correct.add(k)
    print(*sorted(correct), sep='')

import sys
input = sys.stdin.readline

t=int(input())

for test in range(t):

    S=input().strip()+"0"

    NOW=S[0]
    count=1
    ANS=[]

    for i in range(1,len(S)):
        if S[i]==S[i-1]:
            count+=1
        else:
            if count%2==1:
                ANS.append(S[i-1])

            count=1

    ANS=sorted(set(ANS))

    print("".join(ANS))
            


import string

num_inputs = int(input())

for _ in range(num_inputs):
    this_input = input()

    working_letters = []
    for s in string.ascii_lowercase:
        this_input = this_input.replace(s * 2, s.upper())
        if s in this_input:
            working_letters.append(s)
    print("".join(sorted(working_letters)))


t = int(input())

for _ in range(t):
    s = input() + '-'
    ok = {c: False for c in 'qwertyuiopasdfghjklzxcvbnm'}
    cur = 0
    p = ''
    for c in s:
        if c == p:
            cur += 1
        else:
            if cur % 2:
                ok[p] = True
            cur = 1
            p = c
    for c, f in sorted(ok.items()):
        if f:
            print(c, end='')
    print()

T = int(input())

for _ in range(T):
    X = [0] * 26
    s = input()
    while s:
        if len(s) == 1:
            X[ord(s[0])-97] = 1
            break
        if s[0] == s[1]:
            s = s[2:]
        else:
            X[ord(s[0])-97] = 1
            s = s[1:]
    
    print("".join([chr(97+i) for i in range(26) if X[i]]))



t=int(input())
for _ in range(t):
    s=input()
    n=len(s)
    ans=""
    l=""
    ind=0
    while ind<n:
        if ind<n-1:
            if s[ind]==s[ind+1]:
                ind+=2
                continue
            else:
                ans+=s[ind]
                ind+=1
        if ind==n-1:
            ans+=s[ind]
            ind+=1
            
    ans=list(set(list(ans)))
    ans.sort()
    print(''.join(ans))


n = int(input())
for i in range(n):
	st = input()
	st += '#'
	k = len(st)
	lastch = '.'
	lastl = 0
	able = [False for i in range(256)]
	for j in range(k):
		if st[j] != lastch:
			if lastl % 2 == 1:
				able[ord(lastch)] = True
			lastl = 1
			lastch = st[j]
		else:
			lastl += 1
	for j in range(ord('a'),ord('z')+1):
		if able[j]:
			print(chr(j),end='')
	print()

q = int(input())
for i in range(q):
    string = input()
    arr = []
    current = ''
    for index in range(len(string)):
        if not current:
            current += string[index]
            continue
        if string[index] == current[-1]:
            current += string[index]
        else:
            arr.append(current)
            current = string[index]
    if current:
        arr.append(current)
    answer = set()
    for j in arr:
        if len(j) % 2:
            answer.add(j[0])
    print(''.join(sorted(answer)))


n = int(input())

while(n):
    
    S = input()
    S += "_"
    lastChar = ""
    cur = 0
    x = set()
    for s in S:
        if s != lastChar:
            if cur % 2:
                x.add(lastChar)
            lastChar = s
            cur = 1
        else:
            cur += 1
    
    x = list(x)
    x.sort()
    for c in x:
        print(c, end='')
    print()
    
    n -= 1

import sys
import math
from collections import defaultdict
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : map(int, input().split())
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}".format(i) + sep)
INF = float('inf')
MOD = int(1e9 + 7)

for _ in range(int(input())):
  s = input()
  ans = ""
  for i in sorted(set(s)):
    if (not (i+i) in s) or (s.count(i+i)*2 - s.count(i) < 0):
      ans += i 

  print(ans) 

import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int,minp().split())

def solve():
	s = [ord(i) - ord('a') for i in minp()]
	c = [False]*26
	i = 0
	while i < len(s):
		j = i + 1
		while j < len(s) and s[j] == s[i]:
			j += 1
		if (j - i) % 2 == 1:
			c[s[i]] = True
		i = j
	for i in range(26):
		if c[i]:
			print(chr(i+ord('a')), end='')
	print()

for i in range(mint()):
	solve()



for _ in range(int(input())):
	s=input()

	a=[3]*26


	i=0

	while(i<len(s)):
		j=i

		t=0

		while(j<len(s) and s[j]==s[i]):
			j+=1
			t+=1

		if(t&1):
			a[ord(s[i])-ord('a')]=min(0,a[ord(s[i])-ord('a')])
		else:
			a[ord(s[i])-ord('a')]=min(1,a[ord(s[i])-ord('a')])

		i=j

	s=""

	for i in range(26):
		if(a[i]==0):
			s+=chr(97+i)

	print(s)

import sys
import itertools
import math
import collections
from collections import Counter
input = sys.stdin.readline

#########################
# imgur.com/Pkt7iIf.png #
#########################

def sieve(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0] = prime[1] = False
    r = [p for p in range(n + 1) if prime[p]]
    return r
def divs(n, start=1):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def ceil(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return list(map(int, input().split()))
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return collections.defaultdict(int)

t = ii()
for _ in range(t):
    s = input()
    d = Counter(s)
    res = set()
    i = 0
    while i < len(s) - 1:
        j = i + 1
        while j < len(s) - 1 and s[j] == s[j - 1]:
            j += 1
        if (j - i) % 2:
            res.add(s[i])
        i = j
    prr(sorted(list(res)), '')


t=[int(k) for k in input().split(" ")][0]

for k in range(t):
    s=input()
    ss=set()
    k=0
    n=len(s)
    while k<n:
        kk=k
        while kk<n and s[kk]==s[k]:
            kk+=1
        if (kk-k)%2:
            ss.add(s[k])
        k=kk
    print("".join(sorted(list(ss))))


n = int(input())
for i in range(n):
    st = input()
    ans = []
    c = 1
    for j in range(1, len(st)):
        if st[j] == st[j - 1]:
            c += 1
        else:
            if c % 2 == 1:
                if not st[j - 1] in ans:
                    ans.append(st[j - 1])
            c = 1
    if c % 2 == 1:
        if not st[len(st) - 1] in ans:
            ans.append(st[len(st) - 1])
    ans.sort()
    for f in ans:
        print(f, end='')
    print()