Вам задана гирлянда, состоящая из \(n\) ламп. Состояния ламп описываются строкой \(s\) длины \(n\). \(i\)-й символ строки \(s_i\) равен '0', если \(i\)-я лампа выключена, или '1', если \(i\)-я лампа включена. Вам также задано положительное целое число \(k\).
За один ход вы можете выбрать одну лампу и изменить ее состояние (то есть включить ее, если она выключена, и наоборот).
Гирлянда называется \(k\)-периодичной, если расстояние между каждой парой соседних включенных ламп равно в точности \(k\). Рассмотрим случай \(k=3\). Тогда гирлянды «00010010», «1001001», «00010» и «0» являются хорошими, а гирлянды «00101001», «1000001» и «01001100» не являются хорошими. Заметьте, что гирлянда не является цикличной, то есть первая включенная лампа не идет после последней включенной лампы и наоборот.
Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы получить \(k\)-периодичную гирлянду из заданной.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ — минимальное количество ходов, необходимое для того, чтобы получить \(k\)-периодичную гирлянду из заданной.