Задається рядок \(S\) з малих англійський літер, який треба скопіювати в новий рядок \(P\). Можна виконувати наступні операції будь-яку кількість разів:

• перенести будь-який символ з \(S\) в \(P\) за 1 грн

• вибрати будь-який підрядок \(P\) і скопіювати його в кінець \(P\) безкоштовно.

Виконайте копіювання \(S\) в \(P\) за описаними правилами за мінімальну вартість.

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

Перший рядок містить ціле число \(T\) (\(1 \le T \le 5\)) - кількість тестів.

Потім слідують \(T\) рядків, кожен рядок містить рядок \(S\) (\(1 \le |S| \le 10^5\)).

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

У вихідний потік для кожного тесту в окремому рядку вивести  мінімальну вартість копіювання

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

2
abcd
abab

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

4
2