Trova il Successore

Vi viene fornito un elenco di n stringhe. Per ognuna di queste stringhe s, dovete determinare una stringa successiva t presente nello stesso elenco (potendo anche coincidere con s).
La stringa successiva è definita come la stringa più piccola che compaia all’inizio di s.

Input

La prima riga dell’input contiene un singolo intero, n (1 ≤ n ≤ 100 000), che rappresenta il numero di stringhe nell’elenco.

Le successive n righe contengono le stringhe. Ciascuna stringa è formata da lettere minuscole dell’alfabeto inglese.

È garantito che il numero totale di caratteri nell’input non sia superiore a .

Output

Per ogni stringa s in ingresso, stampate in una nuova riga la relativa stringa successiva t.

Esempi

Spiegazione

Per la stringa “abaca” la stringa successiva è “aba”.
Per la stringa “aba”, la successiva è “aba” stessa.
Per la stringa “abacaba” la stringa successiva è “aba”.
Per la stringa “abcab” la stringa successiva è “bacab”.
Per la stringa “dabacaba” la stringa successiva è “dabacaba”.