Trong tin học, thứ tự từ điển là cách sắp xếp các xâu ký tự tương tự như trong từ điển.
Một xâu ký tự ~x~ được coi là lớn hơn xâu ký tự ~y~ nếu ~x~ xuất hiện sau ~y~ trong danh sách sắp xếp theo thứ tự từ điển.

Cho một từ ~w~, hãy tạo ra một từ mới bằng cách hoán đổi một số hoặc tất cả các ký tự của nó. Từ mới này phải thỏa mãn:

• Nó lớn hơn từ gốc ~w~.
• Nó là từ nhỏ nhất thỏa mãn điều kiện trên.

Ví dụ:

• Với ~w = abcd~, từ lớn tiếp theo là ~abdc~.

Input (DICTINARY.INP)

• Dòng 1: số nguyên dương ~T~ là số lượng test (~1 ≤ T ≤ 10^5~).
• ~T~ dòng tiếp theo: mỗi dòng chứa một xâu ký tự ~w~ chỉ gồm các chữ cái latin thường (a–z), độ dài ~1 ≤ |w| ≤ 100~.

Output (DICTINARY.OUT)

• Gồm ~T~ dòng, mỗi dòng chứa kết quả tìm được:
  
  • Xâu ký tự nhỏ nhất lớn hơn từ gốc theo thứ tự từ điển.
  • Nếu không tìm được, in ra "no answer".

Ví dụ

DICTINARY.INP

5
ab
bb
hefg
dhck
dkhc

DICTINARY.OUT

ba
no answer
hegf
dhkc
hcdk

DICTINARY.INP

6
lmno
dcba
dcbb
abdc
abcd
fedcbabcd

DICTINARY.OUT

lmon
no answer
no answer
acbd
abdc
fedcbabdc

Giới hạn

• ~1 ≤ T ≤ 10^5~
• ~1 ≤ |w| ≤ 100~