Космический корабль Бибоп снова остался без денег, и команда охотников за головами берётся за любую работу. На этот раз Спайк и Джет получили странный заказ от технической станции на орбите Ганимеда.

На станции хранится энергетическая строка $$$s$$$, состоящая из строчных латинских букв. Строка разбивается на максимальные блоки одинаковых подряд идущих символов. Если длины этих блоков равны $$$$$$ l_1, l_2, \ldots, l_m \text{,} $$$$$$ то потенциалом строки называется величина $$$$$$ l_1^2 + l_2^2 + \ldots + l_m^2 \text{.} $$$$$$

Например, строка «aaaabbaa» разбивается на блоки длины $$$4$$$, $$$2$$$ и $$$2$$$, поэтому её потенциал равен $$$4^2 + 2^2 + 2^2 = 24$$$.

Чем меньше потенциал строки, тем более безопасно с ней работать. Фэй узнала, что перед выполнением заказа можно аккуратно переместить один символ внутри строки, то есть можно

1. выбрать позицию $$$i$$$;
2. удалить символ $$$s_i$$$ из строки, получив строку $$$s' = s_1 s_2 \ldots s_{i-1} s_{i+1} \ldots s_{|s|}$$$;
3. и затем вставить его в любое место получившейся строки $$$s'$$$: в начало, в конец или между любыми двумя соседними символами.

Всего команде предстоит обработать $$$t$$$ заказов, для каждого заказа — своя строка $$$s$$$. Для каждой строки требуется выполнить не более одной такой операции так, чтобы ее потенциал стал минимально возможным.