Вхідний рядок \(S\) довжиною \(N\) передається по мережі за допомогою спеціального протоколу. Протокол може відправляти рядок через серію операцій. За одну операцію ми можемо вибрати символ нижнього регістру англійського алфавіту \(c\) і виконати одну з таких дій:

• Передати 1 копію \(c\) через мережу.

• Передати через мережу 2 копії \(c\).

Кожна з перерахованих вище передач займає 1 одиницю часу.

Знайти мінімальний час, за який ми можемо передати весь рядок \(S\) через мережу.

Обмеження

• \(1 \leq T \leq 100\)

• \(1 \leq N \leq 10^5\)

• Сума \(N\) за всіма тестами не перевищує \(10^5\).

• Рядок \(S\) містить лише малі літери англійського алфавіту.

Формат вхідних даних

Перший рядок буде містити \(T\) - кількість тестів.

Потім йдуть тестові випадки.

Перший рядок кожного тесту містить \(N\) - довжину рядка \(S\).

Другий рядок кожного тесту містить рядок \(S\).

Формат вихідних даних

Для кожного тесту виведіть в окремому рядку мінімальний час, необхідний для передачі рядка.

Примітка

До тесту 2:

Рядок можна передати за допомогою таких операцій: надіслати 2 копії символу \(\texttt{a}\), надіслати 1 копію символу \(\texttt{b}\), надіслати 1 копію символу \(\texttt{e}\) і надіслати 2 копії символу \(\texttt{e}\). Таким чином, всього потрібно 4 операції.

Приклад вхідних даних

2
5
cbcdc
6
aabeee

Приклад вихідних даних

5
4