Lexicographical order is often known as alphabetical order when dealing with strings.  A string is greater than another string if it comes later in a lexicographically sorted list.

Given a word, create a new word by swapping some or all of its characters.  This new word must meet two criteria:

It must be greater than the original word
It must be the smallest word that meets the first condition

Example 

$w=\textbf{abcd}$

The next largest word is $\textbf{abdc}$.  

Complete the function biggerIsGreater below to create and return the new string meeting the criteria.  If it is not possible, return no answer.

Function Description  

Complete the biggerIsGreater function in the editor below.  

biggerIsGreater has the following parameter(s):  

string w: a word

Returns 

- string: the smallest lexicographically higher string possible or no answer  

Input Format

The first line of input contains $\mathbf{T}$, the number of test cases. 

Each of the next $\mathbf{T}$ lines contains $\boldsymbol{w}$.

Constraints

$1\leq T\leq10^5$  
$1\leq length of w\leq100$  
$\boldsymbol{w}$ will contain only letters in the range ascii[a..z].

Sample Input 0
5
ab
bb
hefg
dhck
dkhc

Sample Output 0
ba
no answer
hegf
dhkc
hcdk

Explanation 0

Test case 1: 

ba is the only string which can be made by rearranging ab. It is greater.   
Test case 2: 

It is not possible to rearrange bb and get a greater string.  
Test case 3: 

hegf is the next string greater than hefg.
Test case 4: 

dhkc is the next string greater than dhck.
Test case 5: 

hcdk is the next string greater than dkhc.

Sample Input 1
6
lmno
dcba
dcbb
abdc
abcd
fedcbabcd

Sample Output 1
lmon
no answer
no answer
acbd
abdc
fedcbabdc

Difficulty: MEDIUM
Tags: Implementation

Starter code:

Solutions:
cases = int(input())
for x in range(cases):
	string = list(input().strip())
	match = False
	for x in range(len(string) - 2, -1, -1):
		if string[x + 1] > string[x]:
			match = True
			for y in range(len(string) - 1, x, -1):
				if string[y] > string[x]:
					(string[x], string[y]) = (string[y], string[x])
					string = string[:x + 1] + sorted(string[x + 1:])
					break
			break
	if match:
		print(''.join(string))
	else:
		print('no answer')


t = int(input())

def lex(a):
	i = len(a) - 2
	while not (i < 0 or a[i] < a[i + 1]):
		i -= 1
	if i < 0:
		print('no answer')
	else:
		j = len(a) - 1
		while not a[j] > a[i]:
			j -= 1
		(a[i], a[j]) = (a[j], a[i])
		a[i + 1:] = reversed(a[i + 1:])
		print(''.join(a))
for i in range(t):
	s = list(input())
	lex(s)


def lexicographically_next_permutation(a):
	i = len(a) - 2
	while not (i < 0 or a[i] < a[i + 1]):
		i -= 1
	if i < 0:
		return False
	j = len(a) - 1
	while not a[j] > a[i]:
		j -= 1
	(a[i], a[j]) = (a[j], a[i])
	a[i + 1:] = reversed(a[i + 1:])
	return True
for _ in range(int(input())):
	s = input()
	arr = list(s)
	if lexicographically_next_permutation(arr):
		print(''.join(arr))
	else:
		print('no answer')


def next_permutation(arr):
	i = len(arr) - 1
	while i > 0 and arr[i - 1] >= arr[i]:
		i -= 1
	if i <= 0:
		return False
	j = len(arr) - 1
	while arr[j] <= arr[i - 1]:
		j -= 1
	(arr[i - 1], arr[j]) = (arr[j], arr[i - 1])
	arr[i:] = arr[len(arr) - 1:i - 1:-1]
	return True
t = int(input())
for i in range(t):
	b = list(input())
	if next_permutation(b):
		for j in range(len(b)):
			print(b[j], end='')
		print('')
	else:
		print('no answer')


def NextPerm(s):
	Len = len(s)
	EndChar = s[Len - 1]
	for i in range(Len - 2, -1, -1):
		c = s[i]
		if c < EndChar:
			buff = s[:i]
			for j in range(Len - 1, i, -1):
				if s[j] > c:
					break
			buff = buff + s[j]
			index = j
			for j in range(Len - 1, i, -1):
				if j == index:
					buff = buff + c
				else:
					buff = buff + s[j]
			return buff
		EndChar = c
	return 'no answer'
T = int(input())
while T != 0:
	s = input()
	print(NextPerm(s))
	T -= 1


def lexicographically_next_word(a):
	i = len(a) - 2
	while not (i < 0 or a[i] < a[i + 1]):
		i -= 1
	if i < 0:
		return False
	j = len(a) - 1
	while not a[j] > a[i]:
		j -= 1
	(a[i], a[j]) = (a[j], a[i])
	a[i + 1:] = reversed(a[i + 1:])
	return True
t = int(input())
if t >= 1 and t <= 100000:
	while t > 0:
		word = input().lower()
		if len(word) >= 1 and len(word) <= 100:
			li = []
			for i in word:
				li.append(i)
			while 1:
				if lexicographically_next_word(li):
					nextword = ''.join(li)
					print(nextword)
				else:
					print('no answer')
				break
		t -= 1


def np(arr):
	i = len(arr) - 1
	while i > 0 and arr[i - 1] >= arr[i]:
		i -= 1
	if i <= 0:
		print('no answer')
		return False
	j = len(arr) - 1
	while arr[j] <= arr[i - 1]:
		j -= 1
	arr = list(arr)
	(arr[i - 1], arr[j]) = (arr[j], arr[i - 1])
	arr[i:] = arr[len(arr) - 1:i - 1:-1]
	arr = ''.join(arr)
	print(arr)
	return True
T = int(input())
for i in range(T):
	a = input()
	np(a)


def logic(word):
	i = len(word) - 1
	while i > 0 and word[i - 1] >= word[i]:
		i -= 1
	if i <= 0:
		return False
	j = len(word) - 1
	while word[j] <= word[i - 1]:
		j -= 1
	(word[i - 1], word[j]) = (word[j], word[i - 1])
	word[i:] = word[len(word) - 1:i - 1:-1]
	return word

def get_next(word, comp):
	i = len(word) - 1
	while i > 0 and comp(word[i - 1], word[i]) >= 0:
		i -= 1
	if i <= 0:
		return False
	j = len(word) - 1
	while comp(word[j], word[i - 1]) <= 0:
		j -= 1
	(word[i - 1], word[j]) = (word[j], word[i - 1])
	word[i:] = word[len(word) - 1:i - 1:-1]
	return True

def process():
	word = list(input())
	word_next = logic(word)
	if not word_next:
		print('no answer')
	else:
		print(''.join(word_next))

def main():
	n = int(input())
	for i in range(n):
		process()
main()


t = int(input())
for i in range(t):
	s = list(input())
	l = len(s)
	p = -1
	for j in range(l - 2, -1, -1):
		if s[j] < s[j + 1]:
			p = j
			break
	if p == -1:
		print('no answer')
	else:
		piv = p
		q = piv
		for j in range(l - 1, piv - 1, -1):
			if s[j] > s[piv]:
				q = j
				break
		t = s[q]
		s[q] = s[piv]
		s[piv] = t
		r = s[piv + 1:]
		r.reverse()
		s = s[:piv + 1] + r
		print(''.join(s))


t = int(input())
for i in range(t):
	a = input()
	l = list(a)
	count = 0
	for j in range(len(a) - 1):
		if ord(l[-(j + 2)]) < ord(l[-(j + 1)]) and j == 0:
			t = l[-1]
			l[-1] = l[-2]
			l[-2] = t
			break
		elif ord(l[-(j + 2)]) < ord(l[-(j + 1)]):
			sort = l[:-(j + 2)] + sorted(l[-(j + 2):])
			min = ''.join(sort).rfind(l[-(j + 2)]) + 1
			t = sort[min]
			sort[min] = sort[-(j + 2)]
			sort[-(j + 2)] = t
			l = sort[:-(j + 1)] + sorted(sort[-(j + 1):])
			break
		elif ord(l[-(j + 2)]) >= ord(l[-(j + 1)]):
			count += 1
	if len(set(a)) == 1 or count == len(a) - 1:
		print('no answer')
	else:
		print(''.join(l))


def main(tests):
	for dummy in range(tests):
		s = input()
		if invariant(s):
			print('no answer')
		else:
			work_horse(s)

def invariant(x):
	i = 0
	while i < len(x) - 1:
		if x[i] < x[i + 1]:
			return False
		i += 1
	return True

def work_horse(string):
	leng = len(string)
	l = leng - 2
	while l >= 0:
		if string[l] < string[l + 1]:
			break
		l -= 1
	i = l
	prev = '{'
	at = 0
	while l < leng:
		if string[l] < prev and string[l] > string[i]:
			prev = string[l]
			at = l
		l += 1
	lst = list(string)
	tmp = lst[i]
	lst[i] = lst[at]
	lst[at] = tmp
	for char in lst[:i + 1]:
		print(char, end='')
	for char in sorted(lst[i + 1:]):
		print(char, end='')
	print()
tsts = int(input())
main(tsts)


def biggerThanChar(c, rst):
	srtd = sorted(rst, reverse=True)
	rind = srtd.index(c) - 1
	if rind >= 0:
		return srtd[rind] + ''.join(sorted(srtd[:rind] + srtd[rind + 1:]))
	else:
		return ''.join(srtd[::-1])

def compute_bigger(line):
	i = len(line) - 1
	while i >= 1:
		if line[i - 1] < line[i]:
			line = line[:i - 1] + biggerThanChar(line[i - 1], line[i - 1:])
			return line
		i -= 1
	return 'no answer'
lines_num = int(input())
for _ in range(lines_num):
	print(compute_bigger(input()))


def main():
	t = int(input())
	res = []
	for i in range(t):
		lex_str = input()
		res.append(NextPerm(lex_str))
	for i in res:
		print(i)

def NextPerm(s):
	Len = len(s)
	EndChar = s[Len - 1]
	for i in range(Len - 2, -1, -1):
		c = s[i]
		if c < EndChar:
			buff = s[:i]
			for j in range(Len - 1, i, -1):
				if s[j] > c:
					break
			buff = buff + s[j]
			index = j
			for j in range(Len - 1, i, -1):
				if j == index:
					buff = buff + c
				else:
					buff = buff + s[j]
			return buff
		EndChar = c
	return 'no answer'
main()


n = int(input())
for i in range(n):
	s = input()
	for i in range(len(s) - 1):
		if s[len(s) - 2 - i] < s[len(s) - 1 - i]:
			j = len(s) - i
			while j < len(s):
				if s[j] <= s[len(s) - 2 - i]:
					break
				j = j + 1
			j = j - 1
			s = s[:len(s) - 2 - i] + s[j] + s[len(s) - 1 - i:j] + s[len(s) - 2 - i] + s[j + 1:]
			s = s[:len(s) - 1 - i] + s[len(s) - 1 - i:][::-1]
			print(s)
			break
	else:
		print('no answer')


def f(st):
	k = -1
	for i in range(len(st) - 2, -1, -1):
		if st[i] < st[i + 1]:
			k = i
			break
	if k == -1:
		return 'no answer'
	st = list(st)
	for j in range(len(st) - 1, -1, -1):
		if st[k] < st[j]:
			(st[k], st[j]) = (st[j], st[k])
			break
	st[k + 1:] = st[k + 1:][::-1]
	return ''.join(st)
for t in range(int(input())):
	print(f(input()))


n = int(input())
for i in range(n):
	s = input()
	l = len(s)
	minpos = l - 1
	chngpos = l - 1
	for j in range(l - 1, 0, -1):
		if s[j - 1] < s[j]:
			minpos = j - 1
			break
	for j in range(l - 1, 0, -1):
		if s[j] > s[minpos]:
			chngpos = j
			break
	w = s[0:minpos] + s[chngpos] + s[minpos + 1:chngpos] + s[minpos] + s[chngpos + 1:]
	w = w[0:minpos + 1] + w[:minpos:-1]
	if len(w) != l:
		print('no answer')
	else:
		print(w)


for _ in range(int(input())):
	s = input()
	s = list(s[::-1])
	done = 0
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			for j in range(i):
				if s[j] > s[i]:
					(s[j], s[i]) = (s[i], s[j])
					s = sorted(s[:i])[::-1] + s[i:]
					print(''.join(s[::-1]))
					break
			break
	else:
		print('no answer')


import sys
T = int(input())
for _ in range(T):
	s = list(input())
	ok = False
	for i in range(len(s) - 2, -1, -1):
		if s[i] < s[i + 1]:
			jMin = i + 1
			distMin = ord(s[jMin]) - ord(s[i])
			for j in range(i + 2, len(s)):
				if s[i] < s[j] and ord(s[j]) - ord(s[i]) < distMin:
					jMin = j
					distMin = ord(s[j]) - ord(s[i])
			tmp = s[i]
			s[i] = s[jMin]
			s[jMin] = tmp
			l = [ord(v) for v in s[i + 1:]]
			l.sort()
			s[i + 1:] = [chr(v) for v in l]
			print(''.join(s))
			ok = True
			break
	if not ok:
		print('no answer')


n = int(input())
il = []
ol = []
j = 0
f = 0
for i in range(n):
	st = input()
	il.append(st)
	j = 0
	f = 0
	if len(st) == 1:
		fstr = 'no answer'
	elif len(st) == 2:
		if st[0] < st[1]:
			fstr = st[1] + st[0]
		else:
			fstr = 'no answer'
	else:
		for j in range(len(st) - 2, -1, -1):
			if st[j] < st[j + 1]:
				f = 1
				break
		if f == 1:
			index = j
			for j in range(len(st) - 1, index, -1):
				if st[j] > st[index]:
					break
			index1 = j
			str1 = st[0:index] + st[index1] + st[index + 1:index1] + st[index] + st[index1 + 1:]
			fstr = str1[0:index + 1] + str1[-1:index:-1]
		else:
			fstr = 'no answer'
	ol.append(fstr)
for s in ol:
	print(s)


def NextPerm(s):
	Len = len(s)
	EndChar = s[Len - 1]
	for i in range(Len - 2, -1, -1):
		c = s[i]
		if c < EndChar:
			buff = s[:i]
			for j in range(Len - 1, i, -1):
				if s[j] > c:
					break
			buff = buff + s[j]
			index = j
			for j in range(Len - 1, i, -1):
				if j == index:
					buff = buff + c
				else:
					buff = buff + s[j]
			return buff
		EndChar = c
	return 'no answer'
t = int(input())
for i in range(t):
	w = input()
	print(NextPerm(w))


def NextPerm(s):
	Len = len(s)
	EndChar = s[Len - 1]
	for i in range(Len - 2, -1, -1):
		c = s[i]
		if c < EndChar:
			buff = s[:i]
			for j in range(Len - 1, i, -1):
				if s[j] > c:
					break
			buff = buff + s[j]
			index = j
			for j in range(Len - 1, i, -1):
				if j == index:
					buff = buff + c
				else:
					buff = buff + s[j]
			return buff
		EndChar = c
	return 'no answer'
t = 0
t = int(input())
while t > 0:
	ink = input()
	print(NextPerm(ink))
	t -= 1


t = int(input())
for k in range(t):
	w = list(input())
	s = -1
	for i in range(0, len(w) - 1):
		if w[i] < w[i + 1]:
			s = i
	e = -1
	for j in range(s + 1, len(w)):
		if w[s] < w[j]:
			e = j
	(w[s], w[e]) = (w[e], w[s])
	a = w[s + 1:]
	a.sort()
	for j in range(s + 1, len(w)):
		w[j] = a[j - s - 1]
	if s == -1:
		print('no answer')
	else:
		print(''.join(w))


num_test_cases = int(input())
from string import ascii_lowercase as alpha
import itertools as it

def pairwise(iterable):
	(a, b) = it.tee(iterable)
	next(b, None)
	return zip(a, b)
position = {letter: alpha.index(letter) for letter in alpha}

def pos(letter):
	return position[letter]

def is_dec(word, order=pos):
	word = pairwise(word)
	for (a, b) in word:
		if order(a) < order(b):
			return False
	return True

def index_to_change(word):
	for i in range(1, len(word)):
		(previous, nxt) = (word[-i], word[-(i + 1)])
		if position[previous] > position[nxt]:
			return i + 1

def separate(word):
	i = index_to_change(word)
	return (word[:-i], word[-i:])

def next_largest(letter, word_ls):
	return min([i for i in word_ls if pos(i) > pos(letter)])

def reordered(suffix):
	copy = list(suffix)
	first_letter = copy.pop(copy.index(next_largest(suffix[0], suffix[1:])))
	the_rest = copy
	the_rest.sort(key=pos)
	new_suffix = first_letter + ''.join(the_rest)
	return new_suffix
for i in range(num_test_cases):
	word = input()
	if is_dec(word):
		print('no answer')
	else:
		(a, b) = separate(word)
		b = reordered(b)
		print(a + b)


testCases = int(input())

def swap(word):
	lengthWord = len(word) - 1
	index = -1
	restWord = ''
	new = []
	while lengthWord != 0:
		restWord = word[index] + restWord
		new = []
		if word[index] > word[index - 1]:
			minElem = min(restWord)
			while minElem <= word[index - 1]:
				new += minElem
				restWord_list = list(restWord)
				restWord_list.remove(minElem)
				restWord = ''.join(restWord_list)
				minElem = min(restWord)
			restWord += word[index - 1]
			restWord_list = list(restWord)
			restWord_list.remove(minElem)
			restWord_list += new
			restWord_list.sort()
			restWord = ''.join(restWord_list)
			word = word[:index - 1] + minElem + restWord
			return word
		lengthWord -= 1
		index -= 1
	return 'no answer'
for _ in range(testCases):
	wordStr = input()
	print(swap(wordStr))


testCases = int(input())

def swap(word):
	lengthWord = len(word) - 1
	index = -1
	restWord = ''
	new = []
	while lengthWord != 0:
		restWord = word[index] + restWord
		new = []
		if word[index] > word[index - 1]:
			minElem = min(restWord)
			while minElem <= word[index - 1]:
				new += minElem
				restWord_list = list(restWord)
				restWord_list.remove(minElem)
				restWord = ''.join(restWord_list)
				minElem = min(restWord)
			restWord += word[index - 1]
			restWord_list = list(restWord)
			restWord_list.remove(minElem)
			restWord_list += new
			restWord_list.sort()
			restWord = ''.join(restWord_list)
			word = word[:index - 1] + minElem + restWord
			return word
		lengthWord -= 1
		index -= 1
	return 'no answer'
for _ in range(testCases):
	wordStr = input()
	print(swap(wordStr))


def NextPerm(s):
	Len = len(s)
	EndChar = s[Len - 1]
	for i in range(Len - 2, -1, -1):
		c = s[i]
		if c < EndChar:
			buff = s[:i]
			for j in range(Len - 1, i, -1):
				if s[j] > c:
					break
			buff = buff + s[j]
			index = j
			for j in range(Len - 1, i, -1):
				if j == index:
					buff = buff + c
				else:
					buff = buff + s[j]
			return buff
		EndChar = c
	return 'no answer'
T = int(input())
W = [input() for i in range(0, T)]
for w in W:
	print(NextPerm(w))


def f(st):
	st = list(st)
	k = -1
	for i in range(len(st) - 2, -1, -1):
		if st[i] < st[i + 1]:
			k = i
			break
	if k == -1:
		return 'no answer'
	p = st[k + 1]
	l = k + 1
	for i in range(k + 2, len(st)):
		if st[i] <= p and st[i] > st[k]:
			p = st[i]
			l = i
	(st[k], st[l]) = (st[l], st[k])
	st[k + 1:] = st[k + 1:][::-1]
	return ''.join(st)
for _ in range(int(input())):
	print(f(input()))


def prius(s):
	w = list(s)
	start = -1
	for i in range(len(w)):
		if i + 1 < len(w) and s[i] < s[i + 1]:
			start = i
	if start == -1:
		print('no answer')
	else:
		end = -1
		for j in range(start + 1, len(w)):
			if w[start] < s[j]:
				end = j
		t = w[start]
		w[start] = w[end]
		w[end] = t
		a = w[start + 1:]
		a.sort()
		for j in range(start + 1, len(w)):
			w[j] = a[j - start - 1]
		print(''.join((x for x in w)))
for i in range(int(input())):
	prius(input())


def lexic(word):
	length = len(word)
	s = list(word)
	for index in range(length - 2, -1, -1):
		letter = word[index]
		for j in range(length - 1, index, -1):
			letter_j = word[j]
			if letter_j > letter:
				s[index] = letter_j
				s[j] = letter
				for k in range(index + 1, length):
					temp = s[k]
					rem_list = list(s[k:length])
					min_letter = min(rem_list)
					min_index = rem_list.index(min_letter)
					s[k + min_index] = temp
					s[k] = min_letter
				return ''.join(s)
	return 'no answer'
number_of_tc = int(input())
for i in range(1, number_of_tc + 1):
	b = input()
	print(lexic(b))


def solve(a):
	a = list(a)
	i = len(a) - 2
	while not (i < 0 or a[i] < a[i + 1]):
		i -= 1
	if i < 0:
		return False
	j = len(a) - 1
	while not a[j] > a[i]:
		j -= 1
	(a[i], a[j]) = (a[j], a[i])
	a[i + 1:] = reversed(a[i + 1:])
	return ''.join(a)
for _ in range(int(input())):
	ans = solve(input().strip())
	if not ans:
		print('no answer')
	else:
		print(ans)


def solve(s):
	s = list(str(s))
	l = len(s)
	r = 'no answer'
	if l >= 2:
		for i in range(1, l):
			if s[l - i] > s[l - i - 1]:
				peg = l - i - 1
				temp = l - i
				for c in range(l - i, l):
					if s[c] > s[peg] and s[c] < s[temp]:
						temp = c
				(s[peg], s[temp]) = (s[temp], s[peg])
				s = s[:peg + 1] + sorted(s[peg + 1:])
				r = ''.join(s)
				break
	return r
num = int(input())
for i in range(num):
	print(solve(input()))


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


count = int(input())

def is_sorted_string(s):
	return sorted(s, reverse=True) == list(s)

def re_arrange(s):
	first = s[0]
	for tc in sorted(s[1:]):
		if tc > first:
			next_c = tc
			break
	lst = list(s)
	lst.remove(next_c)
	lst.sort()
	lst.insert(0, next_c)
	return ''.join(lst)

def solve(s):
	if is_sorted_string(s):
		return 'no answer'
	for k in range(len(s) - 1, -1, -1):
		ss = s[k:]
		if not is_sorted_string(ss):
			return s[:k] + re_arrange(ss)
for _ in range(count):
	s = input()
	print(solve(s))


def np(s):
	for i in range(len(s) - 1, 0, -1):
		if s[i - 1] < s[i]:
			nch = s[i]
			nchi = i
			for j in range(i + 1, len(s)):
				if s[j] > s[i - 1] and s[j] < nch:
					nch = s[j]
					nchi = j
			return s[:i - 1] + nch + ''.join(sorted(s[i - 1:nchi] + s[nchi + 1:]))
	return 'no answer'
for i in range(int(input())):
	print(np(input()))


t = int(input())
t1 = 0
while t1 < t:
	str = input()
	str = list(str)
	i = len(str) - 2
	pos = 0
	while i >= 0:
		if str[i] < str[i + 1]:
			pos = i
			break
		i = i - 1
	i = len(str) - 1
	min = 'zz'
	while i > pos:
		if min > str[i] and str[i] > str[pos]:
			min = str[i]
			pus = i
		i = i - 1
	if min == 'zz':
		print('no answer')
	else:
		str[pus] = str[pos]
		str[pos] = min
		print(''.join(str[0:pos + 1]), end='')
		str = str[pos + 1:]
		str.sort()
		print(''.join(str))
	t1 = t1 + 1


t = int(input())
for i in range(0, t):
	w = input()
	w = list(w)
	l = int(len(w))
	start = -1
	answer = 'no answer'
	for j in range(0, len(w) - 1):
		if w[j] < w[j + 1]:
			start = j
	if start == -1:
		print(answer)
		continue
	end = -1
	for j in range(start + 1, len(w)):
		if w[start] < w[j]:
			end = j
	(w[start], w[end]) = (w[end], w[start])
	a = w[start + 1:]
	a.sort()
	for j in range(start + 1, len(w)):
		w[j] = a[j - start - 1]
	answer = ''.join(w)
	print(answer)


t = int(input())
for k in range(t):
	word = input()
	pos = -1
	for i in range(len(word) - 1, 0, -1):
		if ord(word[i - 1]) < ord(word[i]):
			pos = i - 1
			break
	if pos == -1:
		print('no answer')
	else:
		res = word[:pos]
		lst = list(map(ord, list(word[pos:])))
		successor = None
		for i in range(1, len(lst)):
			if lst[0] < lst[i] and (successor == None or successor > lst[i]):
				successor = lst[i]
		res = res + chr(successor)
		lst.remove(successor)
		lst.sort()
		for el in lst:
			res = res + chr(el)
		print(res)


T = int(input())
words = [str(input()) for k in range(T)]

def next_lex(s):
	start = -1
	for k in range(1, len(s)):
		if s[k - 1] < s[k]:
			start = k
	if start == -1:
		return 'no answer'
	else:
		stop = start
		for k in range(start + 1, len(s)):
			if s[k] > s[start - 1]:
				stop = k
		s = list(s)
		(s[start - 1], s[stop]) = (s[stop], s[start - 1])
		return ''.join(s[0:start] + s[len(s) - 1:start - 1:-1])
for word in words:
	print(next_lex(word))


def bigger_is_better(s):
	size = len(s)
	if size == 1:
		return 'no answer'
	for i in range(1, size):
		if s[-i] > s[-(i + 1)]:
			ans = list(s)
			(n1, c1) = (-(i + 1), s[-(i + 1)])
			n2 = -i
			for j in range(n2 + 1, 0):
				if s[j] <= c1:
					break
				n2 = j
			(ans[n1], ans[n2]) = (s[n2], c1)
			ans[n1 + 1:] = reversed(ans[n1 + 1:])
			ans = ''.join(ans)
			return ans
	return 'no answer'
t = int(input())
for i in range(t):
	s = input()
	print(bigger_is_better(s))


cases = int(input())
for x in range(cases):
	string = list(input())
	found = False
	for i in range(len(string) - 1, 0, -1):
		if string[i - 1] < string[i]:
			left = string[:i]
			right = sorted(string[i:])
			itr = 0
			loopDone = False
			for num in right:
				if left[-1] < right[itr]:
					loopDone = True
					break
				else:
					itr += 1
			if loopDone:
				(left[-1], right[itr]) = (right[itr], left[-1])
				left.extend(right)
				found = True
			break
	if not found:
		print('no answer')
	else:
		print(''.join(left))


import sys
import string
alpha = string.ascii_lowercase
weights = {}

def _find_index(weight, weights_list):
	temp_list = sorted(weights_list)
	for w in temp_list:
		if w > weight:
			return weights_list.index(w)
	return -1

def _find_smallest_greater(sample):
	if len(sample) == 1:
		return sample
	else:
		weight1 = weights[sample[0]]
		sample1 = sample[1:]
		new_weights = [weights[s] for s in sample1]
		index = _find_index(weight1, new_weights)
		if index >= 0:
			result = [sample.pop(index + 1)]
			sample.sort()
			result.extend(sample)
			return result
		else:
			head = [sample.pop(0)]
			sample.sort()
			head.insert(0, sample.pop())
			head.extend(sample)
			return head
i = 1
for char in alpha:
	weights[char] = i
	i += 1
weights['\n'] = 0
T = int(sys.stdin.readline())
for _ in range(T):
	sample = list(sys.stdin.readline())
	if '\n' in sample:
		sample = sample[:-1]
	sample.reverse()
	result = []
	found = False
	for i in range(len(sample) - 1):
		if weights[sample[i]] > weights[sample[i + 1]]:
			found = True
			result = sample[i + 2:]
			break
	if not found:
		print('no answer')
	else:
		result.reverse()
		s = sample[:i + 2]
		s.reverse()
		result.extend(_find_smallest_greater(s))
		print(''.join(result))


def lf(word):
	final = len(word) - 1
	for i in range(final, 0, -1):
		current = word[i - 1]
		in_play = word[i:]
		maximum_in_play = max(in_play)
		if current < maximum_in_play:
			greater_than_current = list(filter(lambda x: x > current, in_play))
			temp = list(word)
			min_index = max([k for k in range(i, len(word)) if temp[k] == min(greater_than_current)])
			(temp[i - 1], temp[min_index]) = (temp[min_index], temp[i - 1])
			temp[i:] = sorted(temp[i:])
			return ''.join(temp)
	return 'no answer'
n = int(input())
for _ in range(n):
	word = input()
	print(lf(word))


def incrementWord(word):
	for i in range(len(word) - 2, -1, -1):
		if word[i] < word[i + 1]:
			for j in range(len(word) - 1, i, -1):
				if word[i] < word[j]:
					return word[:i] + word[j] + (word[i + 1:j] + word[i] + word[j + 1:])[::-1]
	return None
T = int(input())
for t in range(T):
	word = input()
	result = incrementWord(word)
	if result is None:
		print('no answer')
	else:
		print(result)


import sys
test_case = sys.stdin.readlines()

def ordenar(l):
	return ''.join(sorted(l))

def lowest_greater(c, l):
	y = None
	for x in l:
		if y is None:
			if x > c:
				y = x
		elif x > c and x < y:
			y = x
	return y

def greater(l):
	word = l
	l = [x for x in l]
	i = -2
	while i >= -len(l):
		candidate = lowest_greater(l[i], l[i + 1:])
		if candidate is None:
			i -= 1
			continue
		elif candidate > l[i]:
			return word[:i] + candidate + ordenar(word[i + 1:].replace(candidate, l[i], 1))
		i -= 1
	return ''.join(l)
for l in test_case[1:]:
	l = l.strip()
	g = greater(l)
	if g != l:
		print(g)
	else:
		print('no answer')


import sys
N = sys.stdin.readlines()

def mayor(word):
	for i in range(1, len(word)):
		cola = word[-i:]
		if max(cola) <= word[-i - 1]:
			continue
		mayores = []
		for j in range(0, len(cola)):
			if cola[j] > word[-i - 1]:
				mayores.append(cola[j])
		if len(mayores) > 0:
			min_m = min(mayores)
			return (-i, min_m)
	return 'no answer'

def menor(word, indice):
	cola = list(word[indice[0]:])
	cola.remove(indice[1])
	cola.append(word[indice[0] - 1])
	cola.sort()
	return word[:indice[0] - 1] + indice[1] + ''.join(cola)
for line in N[1:]:
	word = line.strip()
	indice = mayor(word)
	if indice == 'no answer':
		print('no answer')
		continue
	print(menor(word, indice))


__author__ = 'danielbaeck'
t = int(input())

def rearr(s):
	start = -1
	for i in range(len(s) - 1):
		if s[i] < s[i + 1]:
			start = i
	if start == -1:
		print('no answer')
		return
	end = -1
	for i in range(start + 1, len(s)):
		if s[start] < s[i]:
			end = i
	(s[start], s[end]) = (s[end], s[start])
	a = s[start + 1:]
	a.sort()
	for i in range(start + 1, len(s)):
		s[i] = a[i - start - 1]
	print(''.join(s))
for i in range(t):
	w = list(input())
	rearr(w)


testCases = int(input())
for i in range(0, testCases):
	string = input()
	flag = 0
	chars = list(string)
	length = len(chars)
	start = -1
	for i in range(0, length - 1):
		if chars[i] < chars[i + 1]:
			start = i
	end = -1
	for j in range(start + 1, len(chars)):
		if chars[start] < chars[j]:
			end = j
	(chars[start], chars[end]) = (chars[end], chars[start])
	a = chars[start + 1:]
	a.sort()
	for j in range(start + 1, len(chars)):
		chars[j] = a[j - start - 1]
	if start != -1:
		print(''.join((x for x in chars)))
	else:
		print('no answer')


def nextBigger(s):
	n = len(s)
	max_c = s[-1]
	for i in range(n - 2, -1, -1):
		if s[i] < max_c:
			(s_j, j) = min((t for t in zip(s[i:], range(i, n)) if t[0] > s[i]))
			return s[:i] + s_j + ''.join(sorted(s[i:j] + s[j + 1:]))
		max_c = s[i]
	return 'no answer'
n = int(input())
for _ in range(n):
	print(nextBigger(input()))


from operator import itemgetter
T = int(input())
for case in range(T):
	S = input()
	swapped = False
	i = len(S)
	max_so_far = float('-inf')
	tuples_examined = []
	while not swapped and i > 0:
		i -= 1
		v = ord(S[i])
		tuples_examined.append((i, v))
		if v < max_so_far:
			jj = sorted(filter(lambda t: t[1] > v, tuples_examined), key=itemgetter(1))[0][0]
			L = S[i:jj] + S[jj + 1:]
			T = S[0:i] + S[jj] + ''.join(sorted(L))
			swapped = True
		elif v > max_so_far:
			max_so_far = v
	print(T if swapped else 'no answer')


def next_lexo(s):
	if ''.join(sorted(s, reverse=True)) == s:
		return 'no answer'
	l = len(s)
	k = -1
	for (i, c) in enumerate(s[-2::-1]):
		if c < s[l - i - 1]:
			k = l - i - 2
			break
	if k == -1:
		raise ValueError('k cannot be -1!')
	c1 = s[k]
	for (i, c) in enumerate(s[:k:-1]):
		if c > c1:
			return s[:k] + s[l - i - 1] + s[:l - i - 1:-1] + s[k] + s[l - i - 2:k:-1]
for _ in range(int(input())):
	print(next_lexo(input()))


num_of_strings = int(input())
for p in range(num_of_strings):
	found = False
	string = list(input())
	if string != sorted(string, reverse=True):
		for i in range(len(string), -1, -1):
			for j in range(len(string) - 1, i - 1, -1):
				for k in range(j, i - 1, -1):
					if string[j] > string[k]:
						tmp = string[k]
						string[k] = string[j]
						string[j] = tmp
						found = True
						string[k + 1:len(string)] = sorted(string[k + 1:len(string)])
					if found:
						break
				if found:
					break
			if found:
				break
	if found:
		print(''.join(string))
	else:
		print('no answer')


T = int(input())
for t in range(T):
	w = input()
	for n in range(len(w) - 2, -2, -1):
		if n == -1:
			break
		if w[n] < w[n + 1]:
			break
	if n == -1:
		print('no answer')
	else:
		new = w[:n]
		ch = []
		for m in range(n, len(w)):
			ch.append(w[m])
		sp = ch[0]
		ch.sort()
		first = sp
		z = 0
		while first == sp:
			z += 1
			first = ch[ch.index(sp) + z]
		new += ch.pop(ch.index(sp) + z)
		for c in ch:
			new += c
		print(new)


def next_permutation(arr):
	i = len(arr) - 1
	while i > 0 and arr[i - 1] >= arr[i]:
		i -= 1
	if i <= 0:
		return 'no answer'
	j = len(arr) - 1
	while arr[j] <= arr[i - 1]:
		j -= 1
	(arr[i - 1], arr[j]) = (arr[j], arr[i - 1])
	arr[i:] = arr[len(arr) - 1:i - 1:-1]
	return ''.join(arr)
for _ in range(int(input())):
	print(next_permutation(list(input())))


t = int(input())
w = [None] * t
for i in range(t):
	w[i] = list(input())
for i in range(t):
	pivot = -1
	alter = 0
	for j in range(len(w[i]) - 1):
		if w[i][j] < w[i][j + 1]:
			pivot = j
	for k in range(len(w[i])):
		if w[i][k] > w[i][pivot]:
			alter = k
	(w[i][pivot], w[i][alter]) = (w[i][alter], w[i][pivot])
	w[i][pivot + 1:] = sorted(w[i][pivot + 1:])
	if pivot == -1:
		print('no answer')
	else:
		print(''.join(w[i]))


def main():
	number_of_test_cases = int(input())
	for test_case in range(number_of_test_cases):
		test_word = list(str(input()))
		test_word_len = len(test_word)
		is_found = False
		for i in range(test_word_len - 1):
			r = test_word_len - i - 1
			l = test_word_len - i - 2
			letter_r = test_word[r]
			letter_l = test_word[l]
			if letter_l < letter_r:
				left_side = test_word[:l + 1]
				right_side = test_word[r:]
				right_side.sort()
				test_word = left_side + right_side
				while True:
					if test_word[l] < test_word[r]:
						break
					r += 1
				(test_word[l], test_word[r]) = (test_word[r], test_word[l])
				is_found = True
				break
		if is_found:
			print(''.join(test_word))
		else:
			print('no answer')
main()


def fA(l):
	if len(l) == 2:
		if l[0] < l[1]:
			return chr(l[1]) + chr(l[0])
		else:
			return 'no answer'
	else:
		last = l[len(l) - 1]
		index = len(l) - 1
		dic = {}
		dic[l[len(l) - 1]] = len(l) - 1
		for i in range(1, len(l)):
			index -= 1
			li = list(dic.keys())
			li.sort()
			for x in li:
				if l[index] < x:
					temp = l[index]
					l[index] = x
					l[dic[x]] = temp
					del temp
					temp = l[index + 1:]
					temp.sort()
					answer = ''
					for i in range(index + 1):
						answer += chr(l[i])
					for i in range(len(temp)):
						answer += chr(temp[i])
					return answer
			dic[l[index]] = index
		return 'no answer'
for T in range(int(input())):
	string = input()
	lis = []
	for i in range(len(string)):
		lis.append(ord(string[i]))
	print(fA(lis))


def next_permutation(lst):
	i = len(lst) - 1
	while i > 0 and lst[i - 1] >= lst[i]:
		i -= 1
	if i <= 0:
		return
	j = len(lst) - 1
	while lst[j] <= lst[i - 1]:
		j -= 1
	(lst[i - 1], lst[j]) = (lst[j], lst[i - 1])
	lst[i:] = lst[len(lst) - 1:i - 1:-1]

def rearrange(s):
	lst = list(s)
	result = lst[:]
	next_permutation(result)
	if lst == result:
		return 'no answer'
	return ''.join(result)
n = int(input())
for _ in range(n):
	s = input()
	print(rearrange(s))


NO_ANSWER = 'no answer'

def solve(s):
	if not s:
		return NO_ANSWER
	x = len(s) - 1
	right = s[x]
	while x:
		x -= 1
		if s[x] < right:
			break
		right = s[x]
	else:
		return NO_ANSWER
	sright = ''.join(sorted(s[x:]))
	(i, ch) = min((i_ch for i_ch in enumerate(sright) if i_ch[1] > s[x]), key=lambda i_ch: i_ch[1])
	return s[:x] + sright[i] + sright[:i] + sright[i + 1:]
for case in range(int(input())):
	s = input()
	print(solve(s))


def next_one(s):
	i = len(s) - 1
	l = 0
	found = False
	while i > 0:
		if s[i - 1] < s[i]:
			l = i - 1
			found = True
			break
		i -= 1
	if not found:
		return 'no answer'
	i = len(s) - 1
	h = 0
	while i > 0:
		if s[i] > s[l]:
			h = i
			break
		i -= 1
	prefix = s[:l]
	return prefix + s[h] + ''.join(sorted(s[l:h] + s[h + 1:]))
for _ in range(int(input())):
	print(next_one(input()))


def lex(s2):
	Slen = len(s2)
	s_tail = ''
	if Slen < 2:
		return 'no answer'
	else:
		for i in range(1, Slen):
			if s2[Slen - i] > s2[Slen - i - 1]:
				s_tail = ''.join(sorted(s_tail + s2[Slen - i] + s2[Slen - i - 1]))
				ix = s_tail.rfind(s2[Slen - i - 1])
				x = s_tail[ix + 1]
				s_tail = s_tail[0:ix + 1] + s_tail[ix + 2:]
				if Slen - i - 1 > 0:
					s2 = s2[0:Slen - i - 1] + x + s_tail
				else:
					s2 = x + s_tail
				return s2
			else:
				s_tail = ''.join(sorted(s_tail + s2[Slen - i]))
		return 'no answer'
T = int(input())
for i in range(T):
	s2 = input()
	print(lex(s2))


from collections import Counter

def solve(s):
	if len(s) < 2:
		return None
	(head, *tail) = s
	solved_tail = solve(tail)
	if solved_tail is None:
		if s[0] >= s[1]:
			return None
		else:
			(new_head, i) = min(((c, i) for (i, c) in enumerate(tail) if c > head))
			res = new_head
			head_inserted = False
			for c in reversed(tail[:i] + tail[i + 1:]):
				if not head_inserted and head < c:
					res += head
					head_inserted = True
				res += c
			if not head_inserted:
				res += head
			return res
	else:
		return head + solved_tail
for _ in range(int(input())):
	res = solve(list(input()))
	if res:
		print(res)
	else:
		print('no answer')


t = int(input())
for _ in range(t):
	word = list(input().strip())
	answer = 'no answer'
	start = -1
	for i in range(0, len(word) - 1):
		if word[i] < word[i + 1]:
			start = i
	if start == -1:
		print('no answer')
		continue
	end = -1
	for j in range(start + 1, len(word)):
		if word[start] < word[j]:
			end = j
	(word[start], word[end]) = (word[end], word[start])
	a = word[start + 1:]
	a.sort()
	for j in range(start + 1, len(word)):
		word[j] = a[j - start - 1]
	print(''.join((x for x in word)))


def rearrange(word):
	if len(word) == 1:
		return 'no answer'
	smallest = word[len(word) - 1]
	lastVal = smallest
	for i in reversed(range(len(word) - 1)):
		if lastVal > word[i]:
			swapCandidates = [x for x in word[i + 1:] if x > word[i]]
			if swapCandidates:
				swapped = min(swapCandidates)
				right = sorted(word[i:])
				right.remove(swapped)
				return word[:i] + swapped + ''.join(right)
		else:
			lastVal = word[i]
	return 'no answer'
numcases = int(input())
for _ in range(numcases):
	print(rearrange(input()))


import sys

def bigger(w):
	word = list(w)
	if len(word) <= 1:
		print('no answer')
	else:
		k = len(word) - 1
		suf = []
		small = word[k]
		suf.append(small)
		k = k - 1
		while k >= 0:
			for i in range(len(suf)):
				if word[k] < suf[i]:
					temp = word[k]
					word[k] = suf[i]
					suf[i] = temp
					suf.sort()
					sufstr = ''.join((x for x in suf if x.isalpha()))
					ans = ''.join(word[0:k + 1])
					print(ans + sufstr)
					return
			suf.append(word[k])
			suf.sort()
			k = k - 1
		print('no answer')
data = sys.stdin.readlines()
n = int(data[0])
for i in range(1, n + 1):
	word = data[i]
	bigger(word)


T = int(input())
for i in range(T):
	s = input()
	l = len(s)
	for i in range(l - 2, -1, -1):
		if s[i] < s[i + 1]:
			for j in range(l - 1, i, -1):
				if s[j] > s[i]:
					print(s[:i] + s[j] + s[l - 1:j:-1] + s[i] + s[j - 1:i:-1])
					break
			break
	else:
		print('no answer')


for _ in range(int(input())):
	S = input()
	(firstindex, secondindex) = (0, 0)
	name = S
	for i in range(len(name) - 1):
		if name[-(i + 1)] > name[-(i + 2)] and (not firstindex):
			firstindex = len(name) - i - 2
			break
	minimum = 30
	for i in range(firstindex, len(name) - 1):
		if ord(name[i + 1]) - ord(name[firstindex]) > 0:
			if minimum > ord(name[i + 1]) - ord(name[firstindex]):
				minimum = ord(name[i + 1]) - ord(name[firstindex])
				secondindex = i + 1
	if firstindex == 0:
		if secondindex == 0:
			print('no answer')
		else:
			name = name[:firstindex] + name[secondindex] + name[firstindex + 1:secondindex] + name[firstindex] + name[secondindex + 1:]
			name = name[:firstindex + 1] + ''.join(sorted(name[firstindex + 1:]))
			print(name)
	else:
		name = name[:firstindex] + name[secondindex] + name[firstindex + 1:secondindex] + name[firstindex] + name[secondindex + 1:]
		name = name[:firstindex + 1] + ''.join(sorted(name[firstindex + 1:]))
		print(name)


import copy
t = int(input())
for i in range(t):
	w = input().strip()
	B = [x for x in w]
	iBreak = -1
	for (i, x) in reversed(list(enumerate(B))):
		if i != 0:
			if B[i] > B[i - 1]:
				iBreak = i - 1
				break
	if iBreak == -1:
		print('no answer')
		continue
	pickFrom = [(i, x) for (i, x) in enumerate(B) if i > iBreak and x > B[iBreak]]
	pickFrom.sort(key=lambda x: x[1])
	iPick = pickFrom[0][0]
	tmp = B[iBreak]
	B[iBreak] = B[iPick]
	B[iPick] = tmp
	pre = B[0:iBreak + 1]
	post = B[iBreak + 1:]
	post.sort(reverse=False)
	print(''.join(pre + post))


for _ in range(0, int(input())):
	line = [x for x in input()]
	found = False
	ans = 'no answer'
	for x in range(len(line) - 1, 0, -1):
		if line[x - 1] < line[x]:
			if x == len(line) - 1:
				(line[x], line[x - 1]) = (line[x - 1], line[x])
			else:
				new_tail = line[x:]
				rep = new_tail.index(min([f for f in new_tail if f > line[x - 1]]))
				(line[x - 1], new_tail[rep]) = (new_tail[rep], line[x - 1])
				new_tail.sort()
				line = line[0:x] + new_tail
			ans = ''.join(line)
			break
	print(ans)


t = int(input())
for i in range(t):
	st = input()
	(flag, j) = (0, 0)
	for j in range(len(st) - 1, 0, -1):
		if st[j - 1] < st[j]:
			flag = 1
			break
	if flag == 0:
		print('no answer')
	else:
		temp = [i for i in st[j - 1:]]
		temp.sort()
		z = 0
		while temp[z] <= st[j - 1]:
			z += 1
		(temp[z], temp[0]) = (temp[0], temp[z])
		temp2 = temp[1:]
		temp2.sort()
		print(st[:j - 1] + temp[0] + ''.join(temp2))


def bigger(string):
	arr = list(string)
	index = None
	for i in range(0, len(arr) - 1)[::-1]:
		if arr[i] < arr[i + 1]:
			index = i
			break
	if index is None:
		return 'no answer'
	for i in range(index, len(arr))[::-1]:
		if arr[i] > arr[index]:
			(arr[index], arr[i]) = (arr[i], arr[index])
			break
	(lo, hi) = (index + 1, len(arr) - 1)
	while lo < hi:
		(arr[lo], arr[hi]) = (arr[hi], arr[lo])
		(lo, hi) = (lo + 1, hi - 1)
	res = ''.join(arr)
	return res
T = int(input())
for _ in range(T):
	s = input().rstrip()
	print(bigger(s))


for _ in range(int(input())):
	answer = []
	chars = list(input())
	for i in range(1, len(chars)):
		if chars[-i] > chars[-i - 1]:
			start = chars[:-i - 1]
			pivot = min([x for x in chars[-i:] if x > chars[-i - 1]])
			end = chars[-i - 1:]
			end.remove(pivot)
			end.sort()
			answer = start + [pivot] + end
			break
	if answer:
		print(''.join(answer))
	else:
		print('no answer')


def printNextBiggestString(s, n):
	if not checkIfDescOrSame(s):
		for i in range(n - 1, -1, -1):
			v = findNextBiggest(s[i], i + 1, s)
			if v != -1:
				sfx = s[i + 1:v] + s[i] + s[v + 1:]
				sfx = ''.join(sorted(sfx))
				print(s[:i] + s[v] + sfx)
				return
	print('no answer')

def findNextBiggest(t, s, x):
	min = -1
	for i in range(s, len(x)):
		if x[i] > t:
			if min == -1 or x[i] < x[min]:
				min = i
	return min

def checkIfDescOrSame(s):
	for i in range(len(s) - 1):
		if s[i] < s[i + 1]:
			return False
	return True
t = int(input())
while t > 0:
	t -= 1
	s = input()
	n = len(s)
	printNextBiggestString(s, n)


def find_start(chars):
	start = -1
	for i in range(0, len(chars) - 1):
		if chars[i] < chars[i + 1]:
			start = i
	return start

def find_end(chars, start):
	end = -1
	for j in range(start + 1, len(chars)):
		if chars[start] < chars[j]:
			end = j
	return end

def main(strings):
	for the_str in strings:
		chars = list(the_str)
		start = find_start(chars)
		end = find_end(chars, start)
		(chars[start], chars[end]) = (chars[end], chars[start])
		a = chars[start + 1:]
		a.sort()
		for j in range(start + 1, len(chars)):
			chars[j] = a[j - start - 1]
		if start != -1:
			print(''.join(chars))
		else:
			print('no answer')
tests = int(input())
strings = []
for t in range(tests):
	strings.append(input().lower())
main(strings)


def findAnswer(s):
	for n in range(-1, -len(s), -1):
		if s[n] > s[n - 1]:
			a = s[:n - 1]
			bs = sorted(s[n - 1:], reverse=True)
			x = bs[bs.index(s[n - 1]) - 1]
			bs.remove(x)
			bs.reverse()
			return a + x + ''.join(bs)
	return 'no answer'
anz = int(input())
for i in range(anz):
	s = input()
	print(findAnswer(s))


class Node:

	def __init__(self, val, i, left=None, right=None):
		self.r = right
		self.l = left
		self.val = val
		self.i = i

	def __repr__(self):
		return str(self.val) + ':' + str(self.i)

	def __eq__(self, other):
		return self.val == other.val

	def __lt__(self, other):
		return self.val < other.val

	def __gt__(self, other):
		return self.val > other.val

	def __le__(self, other):
		return self.val <= other.val

	def __hash__(self):
		return hash(self.val)
for _ in range(int(input())):
	line = list(input().strip())
	max_ = root = Node(line[-1], len(line) - 1)
	nv = set([root])
	done = False
	for i in range(len(line) - 1, -1, -1):
		z = Node(line[i], i)
		nv.add(z)
		if z >= max_:
			max_ = z
			continue
		for k in sorted(nv):
			if k > z:
				break
		(line[i], line[k.i]) = (line[k.i], line[i])
		line[i + 1:] = sorted(line[i + 1:])
		print(''.join(line))
		done = True
		break
	if not done:
		print('no answer')


t = int(input())

def biggerIsGreater(inputString):
	visited = []
	biggest = -1
	answer = 'no answer'
	for (index, char) in enumerate(reversed(inputString)):
		if ord(char) < biggest:
			stringArray = list(reversed(inputString))
			for (visitedIndex, visitedChar) in enumerate(visited):
				if char < visitedChar:
					(stringArray[index], visited[visitedIndex]) = (visitedChar, char)
					break
			stringArray = list(reversed(stringArray[index:])) + visited
			answer = ''.join(stringArray)
			break
		else:
			biggest = ord(char)
			visited.append(char)
	return answer
arr = []
for _ in range(t):
	print(biggerIsGreater(str(input())))


t = int(input())
assert 1 <= t <= 10 ** 5

def greater(string1):
	tmpList = list(string1)
	largest = -1
	for i in range(len(string1)):
		if ord(string1[-1 - i]) < ord(string1[largest]):
			tmp = largest
			for j in range(i - 1):
				if ord(string1[-1 - j]) > ord(string1[-1 - i]) and ord(string1[-1 - j]) < ord(string1[tmp]):
					tmp = -1 - j
			tmpList[-1 - i] = string1[tmp]
			tmpList[tmp] = string1[-1 - i]
			tmpList[-i:] = sorted(tmpList[-i:])
			return ''.join(tmpList)
		if ord(string1[-1 - i]) > ord(string1[largest]):
			largest = -1 - i
	return 'no answer'
for i in range(t):
	w = str(input())
	assert 1 <= len(w) <= 100
	print(greater(w))


for t in range(int(input())):
	w = input()
	lw = list(w)
	i = len(w) - 1
	nw = ''
	while i:
		i -= 1
		if w[i] < w[i + 1]:
			nw = w[:i]
			minv = min([x for x in lw[i + 1:] if x > w[i]])
			nw += minv
			end = lw[i + 1:]
			end.remove(minv)
			end.append(w[i])
			nw += ''.join(sorted(end))
			break
	print(nw or 'no answer')


def swap_letters(s, i, j):
	res = s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
	return res

def greater(s):
	is_possible = False
	n = len(s)
	for x in range(n - 1):
		if ord(s[x]) < ord(s[x + 1]):
			is_possible = True
	if not is_possible:
		return 'no answer'
	else:
		for x in range(n - 1, 0, -1):
			if ord(s[x - 1]) < ord(s[x]):
				pos_i = x - 1
				break
		for x in range(n - 1, pos_i, -1):
			if ord(s[x]) > ord(s[pos_i]):
				pos_j = x
				break
		s = swap_letters(s, pos_i, pos_j)
		result = s[:pos_i + 1] + ''.join(sorted(s[pos_i + 1:]))
		return result

def main():
	t = int(input())
	for x in range(t):
		w = input()
		print(greater(w))
main()


def ssort(s):
	return ''.join(sorted(s))
count = int(input().strip())
for i in range(count):
	s = input()
	ln = len(s)
	ns = None
	ls = [' '] * ln
	maxc = s[ln - 1]
	for l in range(ln - 1, -1, -1):
		if s[l] > maxc:
			maxc = s[l]
		ls[l] = maxc
	for l in range(ln - 2, -1, -1):
		c = s[l]
		leastc2 = None
		leastm = -1
		if ls[l + 1] > c:
			for m in range(l + 1, ln):
				c2 = s[m]
				if c2 > c:
					if leastc2 == None or c2 < leastc2:
						leastc2 = c2
						leastm = m
		if leastc2 != None:
			ns = s[0:l] + leastc2
			suffix = c + s[l + 1:leastm] + s[leastm + 1:ln]
			ssuffix = ssort(suffix)
			ns = ns + ssuffix
			break
	if ns == None:
		print('no answer')
	else:
		print(ns)


def bigger_greater(w):
	w = list(w)
	for i in range(len(w) - 1, -1, -1):
		for j in range(len(w) - 1, i, -1):
			if w[i] < w[j]:
				(w[i], w[j]) = (w[j], w[i])
				return ''.join(w[:i + 1] + sorted(w[i + 1:]))
	return 'no answer'
for _ in range(int(input())):
	word = input()
	print(bigger_greater(word))


def solve(s):
	s = list(s)
	l = len(s) - 1
	for i in range(len(s) - 1, 0, -1):
		if s[i] > s[i - 1]:
			ss = sorted(s[i - 1:])
			j = 0
			while ss[j] <= s[i - 1]:
				j += 1
			return ''.join(s[:i - 1] + [ss[j]] + ss[:j] + ss[j + 1:])
	return 'no answer'
T = int(input())
for _ in range(T):
	print(solve(input()))


def find_succ(char, char_freq):
	for i in range(ord(char) + 1, 123):
		c1 = chr(i)
		if c1 in char_freq:
			return (True, c1)
	return (False, None)

def next_greatest_word(word):
	new_word = ''
	char_freq = {word[-1]: 1}
	start_char = len(word) - 2
	for index in range(start_char, -1, -1):
		c1 = word[index]
		if c1 in char_freq:
			char_freq[c1] += 1
		else:
			char_freq[c1] = 1
		succ = find_succ(c1, char_freq)[1]
		if succ is not None:
			char_freq[succ] -= 1
			new_word = word[:index] + succ
			break
	else:
		return 'no answer'
	from string import ascii_lowercase
	for c2 in ascii_lowercase:
		if c2 in char_freq and char_freq[c2] > 0:
			new_word += c2 * char_freq[c2]
	return new_word

def main():
	num_cases = int(input().strip())
	for i in range(num_cases):
		word = input().strip()
		print(next_greatest_word(word))
main()


def rearrange(s, i):
	for j in range(i + 1, len(s)):
		if s[i] < s[j]:
			return s[0:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
	return s[0:i] + s[i + 1:] + s[i]

def sg(s):
	t = s
	for i in range(len(t) - 2, -1, -1):
		t = rearrange(t, i)
		if t > s:
			return t
	return 'no answer'
for i in range(int(input())):
	print(sg(input()))


n = int(input())
for _ in range(n):
	x = input()
	i = len(x) - 2
	rearranged = False
	while i >= 0:
		if x[i + 1] > x[i]:
			right_side_arr = ''.join(sorted(x[i + 1:]))
			j = 0
			while j < len(right_side_arr):
				if right_side_arr[j] > x[i]:
					break
				j = j + 1
			right_side = right_side_arr[j] + right_side_arr[:j] + x[i] + right_side_arr[j + 1:]
			x = x[:i] + right_side
			rearranged = True
			break
		i = i - 1
	if rearranged:
		print(x)
	else:
		print('no answer')


def bigger_is_greater():
	test_cases = int(input())
	for t in range(test_cases):
		word = input()
		for i in reversed(range(len(word) - 1)):
			if word[i] < word[i + 1]:
				break
		else:
			print('no answer')
			continue
		min_replacement = i + 1
		for j in range(i + 2, len(word)):
			if word[j] > word[i] and word[j] < word[min_replacement]:
				min_replacement = j
		sequence = list(word)
		(sequence[i], sequence[min_replacement]) = (sequence[min_replacement], sequence[i])
		(first_half, second_half) = (sequence[:i + 1], sequence[i + 1:])
		second_half.sort()
		first_half.extend(second_half)
		print(''.join(first_half))
bigger_is_greater()


loops = int(input())
for loop in range(loops):
	word = list(input())
	temp = list()
	s = len(word)
	flag = False
	for index in range(s):
		letter = word.pop(s - 1 - index)
		temp.insert(0, letter)
		temp.sort()
		ss = len(temp) - 1
		if letter < temp[ss]:
			for index in range(ss, -1, -1):
				if letter >= temp[index]:
					word.append(temp[index + 1])
					temp.pop(index + 1)
					temp.sort()
					word.extend(temp)
					flag = True
					break
		if flag:
			break
	if flag:
		print(''.join(map(str, word)))
	else:
		print('no answer')


def nextPermutation(string):
	string = [x for x in string]
	n = len(string)
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i, -1):
			if string[j] > string[i]:
				(string[j], string[i]) = (string[i], string[j])
				right = sorted(string[i + 1:])
				return ''.join(string[:i + 1] + right)
	return 'no answer'
reps = int(input())
for _ in range(reps):
	print(nextPermutation(input()))


def lex_greater(st):
	for i in range(-1, -1 * len(st), -1):
		if ord(st[i]) > ord(st[i - 1]):
			pivot = i - 1
			for j in range(-1, -1 * len(st), -1):
				if ord(st[j]) > ord(st[pivot]):
					succ = j
					if succ == -1:
						return st[:pivot] + st[succ] + (st[pivot + 1:succ] + st[pivot])[::-1]
					else:
						return st[:pivot] + st[succ] + (st[pivot + 1:succ] + st[pivot] + st[succ + 1:])[::-1]
	return 'no answer'

def main():
	T = int(input())
	for case in range(T):
		st = input()
		print(lex_greater(st))
main()


t = int(input())

def nextLex(s):
	for j in range(len(s) - 2, 0 - 1, -1):
		for k in range(len(s) - 1, j, -1):
			if s[j] < s[k]:
				o = s[:j] + s[k]
				r = s[j:k] + s[k + 1:]
				print(o + ''.join(sorted(r)))
				return
	print('no answer')
for i in range(t):
	s = input().strip()
	nextLex(s)


T = int(input())
for _ in range(T):
	s = list(input())
	noAnswer = True
	mx = 'a'
	for i in range(len(s) - 1, -1, -1):
		if mx > s[i]:
			noAnswer = False
			break
		mx = max(mx, s[i])
	if noAnswer:
		print('no answer')
		continue
	mn = 'z'
	k = -1
	for j in range(i + 1, len(s)):
		if s[j] > s[i] and (k == -1 or s[j] < mn):
			mn = s[j]
			k = j
	(s[i], s[k]) = (s[k], s[i])
	s[i + 1:] = sorted(s[i + 1:])
	print(''.join(s))


t = int(input())
for _ in range(t):
	s = input()
	ln = len(s)
	c = s[ln - 1]
	check = -1
	index = -1
	if ln != 1:
		for i in range(len(s) - 2, -1, -1):
			if ord(c) > ord(s[i]):
				index = i
				check = 1
				break
			c = s[i]
	if check == -1:
		print('no answer')
	else:
		front = s[:index]
		tmp = s[index:]
		ori = tmp[0]
		li = sorted(list(tmp))
		for i in li:
			if ord(i) > ord(ori):
				front += i
				li.remove(i)
				break
		front += ''.join(li)
		print(front)


def next_lex_permutation(string):
	l = len(string)
	j = l - 1
	while j - 1 >= 0 and ord(string[j - 1]) >= ord(string[j]):
		j -= 1
	if j <= 0:
		return 'no answer'
	pivot = j - 1
	j = l - 1
	while ord(string[j]) <= ord(string[pivot]):
		j -= 1
	swap_element = j
	(string[pivot], string[swap_element]) = (string[swap_element], string[pivot])
	(prefix, suffix) = (string[0:pivot + 1], string[pivot + 1:])
	string = ''.join(prefix + sorted(suffix))
	return string
T = int(input())
for _ in range(T):
	string = input()
	print(next_lex_permutation(list(string)))


numStr = int(input())
for i in range(numStr):
	s = input()
	if len(s) == 1:
		print('no answer')
	else:
		pivot = -1
		for j in range(len(s) - 1, 0, -1):
			if s[j] > s[j - 1]:
				pivot = j - 1
				break
		if pivot == -1:
			print('no answer')
		else:
			for j in range(len(s) - 1, pivot, -1):
				if s[pivot] < s[j]:
					s = s[:pivot] + s[j] + s[pivot + 1:j] + s[pivot] + s[j + 1:]
					temp = []
					temp2 = list(s[pivot + 1:])
					for t in range(len(temp2)):
						temp.append(temp2.pop())
					s = s[:pivot + 1] + ''.join(temp)
					break
			print(s)


def is_sorted(s):
	for i in range(1, len(s)):
		if s[i - 1] < s[i]:
			return False
	return True

def f(s):
	if is_sorted(s):
		return 'no answer'
	t = list(s)
	for i in range(len(s) - 2, -1, -1):
		u = sorted(t[i + 1:])
		for j in range(len(u)):
			if t[i] < u[j]:
				m = u[j]
				u[j] = t[i]
				return ''.join(t[:i] + [m] + u)
	return 'no answer'
for i in range(int(input())):
	print(f(input()))


ans = []
t = int(input())
iter = 0
while iter < t:
	iter += 1
	s = [ord(c) for c in input()]
	len_s = len(s)
	if len_s == 1:
		print('no answer')
		continue
	if len_s == 2:
		if s[1] > s[0]:
			print(chr(s[1]) + chr(s[0]))
		else:
			print('no answer')
		continue
	wumbo = 0
	while wumbo < len_s - 1:
		if s[wumbo] < s[wumbo + 1]:
			break
		wumbo += 1
	else:
		print('no answer')
		continue
	for i in range(len_s - 2, -1, -1):
		for i2 in range(len_s - 1, i, -1):
			if s[i] < s[i2]:
				s.insert(i, s.pop(i2))
				s = s[:i + 1] + s[-1:i:-1]
				for i3 in range(i + 1, len_s - 1):
					if s[-1] < s[i3]:
						s.insert(i3, s.pop(-1))
				print(''.join([chr(c) for c in s]))
				break
		else:
			continue
		break
	else:
		print('no answer')


def nearest_greater_tail(letter, letters):
	if letters is None or len(letters) == 0:
		return None
	nearest_greater = None
	for other in letters:
		if other != letter and other > letter:
			if nearest_greater is None or nearest_greater > other:
				nearest_greater = other
	if nearest_greater is not None:
		tail = sorted(letters + letter)
		tail.remove(nearest_greater)
		return nearest_greater + ''.join(tail)
	else:
		return None

def next_largest_rearranging(word=''):
	if len(word) <= 1:
		return 'no answer'
	current_position = len(word) - 2
	while current_position >= 0:
		possibility = nearest_greater_tail(word[current_position], word[current_position + 1:])
		if possibility is not None:
			return word[0:current_position] + possibility
		current_position -= 1
	return 'no answer'
lines = int(input().strip())
for i in range(lines):
	word = input().strip()
	print(next_largest_rearranging(word))


for t in range(int(input())):
	w = [x for x in input()]
	for i in range(len(w) - 1, 0, -1):
		if w[i] > w[i - 1]:
			s = w[i - 1:len(w)]
			r = '0'
			for c in reversed(s):
				if c > w[i - 1]:
					r = c
					s.remove(c)
					break
			print(''.join(w[:i - 1]) + r + ''.join(sorted([x for x in s])))
			break
	else:
		print('no answer')


import copy

def permute_in_place(a):
	yield list(a)
	if len(a) <= 1:
		return
	first = 0
	last = len(a)
	while 1:
		i = last - 1
		while 1:
			i = i - 1
			if a[i] < a[i + 1]:
				j = last - 1
				while not a[i] < a[j]:
					j = j - 1
				(a[i], a[j]) = (a[j], a[i])
				r = a[i + 1:last]
				r.reverse()
				a[i + 1:last] = r
				yield list(a)
				break
			if i == first:
				a.reverse()
				return
n = int(input())
for _ in range(n):
	s = [c for c in str(input())]
	s_copy = copy.deepcopy(s)
	l = permute_in_place(s)
	answer = False
	for x in l:
		perm_str = ''.join(x)
		if perm_str > ''.join(s_copy):
			answer = True
			break
	if answer:
		print(perm_str)
	else:
		print('no answer')