В ЛКШ.Зима день экскурсий, поэтому \(t\) групп школьников отправились в Торжок. Тротуары в Торжке настолько узкие, что идти приходится в колонне по-одному.
Изначально некоторые из школьников злы. Для удобства будем описывать группу школьников строкой из заглавных латинских букв «A» и «P»:
- «A» соответствует злому школьнику
- «P» соответствует спокойному школьнику
Строка описывает школьников от последнего к первому, слева направо.
Каждую минуту каждый злой школьник кидает снежок в спину идущего непосредственно перед ним.
Формально, если злой школьник соответствует символу заданной строки с индексом \(i\), то снежок он будет кидать в школьника, который соответствует символу с индексом \(i+1\) (студенты в строке заданы от последнего к первому!). Если школьник, в которого попали снежком, еще не был зол, то он становится злым. Даже если первый (самый правый в строке) школьник является злым, он не бросает снежок, так как впереди него нет другого ученика.
Рассмотрим первый тестовый пример. В нем колонна изначально имеет такой вид: PPAP. Через минуту единственный злой школьник кинет снежок в школьника, идущего перед ним, и он тоже станет злым: PPAA. После этого, новых злых школьников появляться не будет.
Помогите преподавателям ЛКШ.Зима определить для каждой группы время, спустя которое в ней появится последний злой школьник.
Примечание
В первом примере через \(1\) минуту состояния школьников станут такими: PPAA после этого новых злых школьников не появится.
Во втором примере состояния школьников в первой группе по минутам будут выглядеть так:
- через \(1\) минуту — AAPAAPPAAPPP
- через \(2\) минуты — AAAAAAPAAAPP
- через \(3\) минуты — AAAAAAAAAAAP
- через \(4\) минуты злыми станут все \(12\) школьников, поэтому новых злых школьников не появится.
Во второй группе второго примера через \(1\) минуту все школьники станут злыми.