У вас есть пароль, который вы часто набираете — строка \(s\) длины \(n\), состоящая из первых \(m\) букв латинского алфавита.
Из-за того, что вы много времени тратите на набор этого пароля, вы хотите купить новую клавиатуру.
Клавиатура — это перестановка первых \(m\) букв латинского алфавита. Например, если \(m = 3\), то существует всего шесть различных клавиатур: abc, acb, bac, bca, cab и cba.
Так как вы набираете пароль одним пальцем, вам нужно тратить время на перемещение этого пальца от одного символа пароля к другому. Время перемещения пальца от символа \(s_i\) к символу \(s_{i+1}\) равно дистанции между этими символами на клавиатуре. Суммарное потраченное время на набор пароля называется медлительностью.
Формально, медлительность клавиатуры равна \(\sum\limits_{i=2}^{n} |pos_{s_{i-1}} - pos_{s_i} |\), где \(pos_x\) — позиция символа \(x\) на клавиатуре.
Например, если \(s\) = aacabc, а клавиатура равна bac, то медлительность клавиатуры равна \(|pos_a - pos_a| + |pos_a - pos_c| + |pos_c - pos_a| + |pos_a - pos_b| + |pos_b - pos_c|\) = \(|2 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 3|\) = \(0 + 1 + 1 + 1 + 2 = 5\).
До того как купить клавиатуру, вы хотите знать ее минимально возможную медлительность.
Примечание
Первый тестовый пример разобран в условии.
Во втором тестовом примере медлительность любой клавиатуры равна \(0\).
В третьем тестовом одна из подходящих клавиатур — bacd.