Сплоченность в IT
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Совет топ-менеджеров одной известной IT компании решил, что для повышения эффективности работы необходимо улучшить взаимодействие между командами. Для этого в пятницу было организовано мероприятие по сплочению сотрудников. На мероприятие собрали сотрудников из 26 команд, каждая из которых обозначалась уникальной латинской буквой от 'a' до 'z'. Затем всех сотрудников, пришедших на мероприятие, выстроили в ряд. Для каждого сотрудника записали букву, соответствующую его команде, в результате чего получилась строка длины $$$n$$$, состоящая из латинских строчных символов.

Сотрудники из одной команды уже знакомы друг с другом, поэтому целью мероприятия стало познакомить людей из разных команд. Поскольку сотрудников было слишком много, решено было знакомить только тех программистов, которые являются соседями в ряду и работают в соседних командах. Соседними командами являются те, чьи буквы расположены подряд в алфавите. Например, 'a' и 'b', 'e' и 'd' — это пары соседних команд, а 'z' и 'a', 'd' и 'f', 't' и 't' соседними не считаются.

Для того чтобы процесс знакомства был более организованным и последовательным, было решено следующее: среди всех соседей, которые соответствуют условию для знакомства, выбиралась первая подходящая пара. Затем один из сотрудников этой пары исключался из ряда, а остальные сдвигались, занимая его место. При этом исключался сотрудник с буквой, которая идет позже в алфавите — то есть из пары удалялся сотрудник с максимальной буквой, а оставался тот, чья буква идет раньше в алфавите. Это правило позволяло сохранять упорядоченность строки и помогало равномерно знакомить сотрудников из разных команд.

Все детали были продуманы, теперь осталось понять, какая последовательность сотрудников останется в конце, для этого к вам обратились за помощью.

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов.

В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество сотрудников на мероприятии.

Во второй строке вводится строка из $$$n$$$ латинских строчных символов $$$s_1s_2\ldots s_{n}$$$ — последовательность команд сотрудников в ряду.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите команды оставшихся людей в ряду.

Пример

Входные данные

    55bdcef3hgf7dbbdcaz4cbab8abebbcab

Выходные данные

    be
    f
    daz
    a
    aea

Примечание

В первом наборе входных данных ряд меняется следующим образом : 'bdcef' $$$\rightarrow$$$ 'bcef' $$$\rightarrow$$$ 'bef' $$$\rightarrow$$$ 'be'

В третьем наборе входных данных ряд меняется следующим образом : 'dbbdcaz' $$$\rightarrow$$$ 'dbbcaz' $$$\rightarrow$$$ 'dbbaz' $$$\rightarrow$$$ 'dbaz' $$$\rightarrow$$$ 'daz'