greater-bigger-1

Given a word w, rearrange the letters of w to construct another word s in such a way that s is lexicographic-ally greater than w. In case of multiple possible answers, find the lexicographic-ally smallest one.

Input Format

The first line of input contains t, the number of test cases. Each of the next t lines contains w.

Output Format

For each testcase, output a string lexicographically bigger than w in a separate line. In case of multiple possible answers, print the lexicographically smallest one, and if no answer exists, print no answer.

Constraints

1≤t≤105

1≤|w|≤100

w will contain only lower-case English letters and its length will not exceed 100.

SAMPLE INPUT
5
ab
bb
hefg
dhck
dkhc

SAMPLE OUTPUT
ba
no answer
hegf
dhkc
hcdk

Explanation

Test case 1:

There exists only one string greater than 'ab' which can be built by   rearranging  'ab'. That is 'ba'.

**Test case 2:**

Not possible to rearrange 'bb' and get a lexicographically greater string.

**Test case 3:**

'hegf' is the next string lexicographically greater than 'hefg'.

**Test case 4:**

'dhkc' is the next string lexicographically greater than 'dhck'.

**Test case 5:**

'hcdk' is the next string lexicographically greater than 'dkhc'.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
t=eval(input())
for _ in range(t):
	s=input()
	s=list(s)
	q=1
	l=0
	for i in range(len(s)-1,0,-1):
		if s[i]>s[i-1]:
			k=i-1
			q=0
			break
	if(q==1):
		print("no answer")
		continue
	
	for i in range(len(s)-1,k,-1):
		if s[i]>s[k]:
			l=i
			break
	s[k],s[l]=s[l],s[k]
	s[k+1:len(s)]=reversed(s[k+1:len(s)])
	print(''.join(s))
	


cases = int(input())
 
for case in range(0,cases):
	st = input()
	s = list(st)
	l = len(s)
	boo = True
	v = 0
	
	for i in range(1,l):
		if s[l-i] > s[l-i-1]:
			v = l-i
			break
	
	for j in range(1,l):
		if s[l-j] > s[l-i-1]:
			s[l-j], s[l-i-1] = s[l-i-1], s[l-j]
			break
	
	
	
	
	
	if v == 0 :
		print("no answer")
	else:
			
		s1 = sorted(s[v:])
		s2 = s[:v]
		for ele in s1:
			s2.append(ele)
		st1 = ''.join(s2)
		
		if st1 == st:
			print("no answer")
		else:
			print(st1)
		


from itertools import permutations

z=[]
for i in range(eval(input())):
	t=input()
	perms = [''.join(p) for p in permutations(t)]
	perms.sort()
	for i in perms:
		z=i
		if(z.count(z[0]) == len(t)):
			print("no answer")
			break
		if(i>t):
			print(i)
			break
		
			
		




from itertools import permutations
num = int(input())
for i in range(num):
	flag = "False"
	word = input()
	perms = [''.join(p) for p in permutations(word)]
	perms.sort()
	for wrd in perms:
		if wrd > word:
			print(wrd)
			flag = "True"
			break
		
	if flag == "False":
		print("no answer")
	


from itertools import permutations
def get(s):
	A = list(s)
	A = list(map(ord, A))
	n = len(A)
 
	a = -1
	for i in range(n-1, 0, -1):
		if A[i-1]<A[i]:
			a = i-1
			break
	else:
		return "no answer"
 
	b = -1
	for i in range(n-1, a, -1):
		if A[i]>A[a]:
			b = i
			break
	else:
		return "no answer"
	A[a], A[b] = A[b], A[a]  
	A = A[:a+1]+A[n-1:a:-1] 
	return "".join(map(chr, A))
for _ in range(eval(input())):
	s=input()
	print(get(s))
   


# Enter your code here. Read input from STDIN. Print output to STDOUT
t = int(input())

for _ in range(t):
	w = list(input())
	l = len(w)
	
	i = l - 1
	while i > 0 and w[i-1] >= w[i]:
		i-=1
	
	if i<=0:
		print("no answer")
		continue
	
	j = l - 1
	while w[j]<= w[i-1]:
		j-=1
	
	w[i-1],w[j] = w[j],w[i-1]
	
	print("".join( w[:i]+w[i:][::-1]))
		


def Permute(string):
	if len(string) == 0:
		return ['']
	prevList = Permute(string[1:len(string)])
	nextList = []
	for i in range(0,len(prevList)):
		for j in range(0,len(string)):
			newString = prevList[i][0:j]+string[0]+prevList[i][j:len(string)-1]
			if newString not in nextList:
				nextList.append(newString)
	return nextList

if __name__=='__main__':
	T = int(input())
	for i in range(0,T):
		string = input()
		lst = Permute(string)
		lst = sorted(lst)
		count = lst.index(string)+1
		if count == len(lst):
			print("no answer")
		else:
			print(lst[count])