Вы попали на необычный перекресток со странным светофором. У этого светофора есть три возможных цвета: красный (r), желтый (y), зеленый (g). Известно, что светофор повторяет свои цвета каждые \(n\) секунд и в \(i\)-ю секунду горит цвет \(s_i\).
Таким образом, порядок цветов задаётся строкой. Например, если \(s=\)«rggry», то светофор горит так: красный-зеленый-зеленый-красный-желтый-красный-зеленый-зеленый-красный-желтый- ... и так далее.
Более формально, вам дана строка \(s_1, s_2, \ldots, s_n\) длины \(n\). В первую секунду горит цвет \(s_1\), во вторую \(s_2\), ..., в \(n\)-ю секунду горит цвет \(s_n\), в \(n + 1\)-ю секунду горит цвет \(s_1\) и так далее.
Вам нужно перейти дорогу, и это можно сделать только тогда, когда на светофоре горит зеленый цвет.
Вам известно, какой сейчас цвет на светофоре, но вы не знаете текущей момент времени. Вам нужно найти минимальное время, в течение которого вы точно (наверняка) сможете перейти дорогу.
Можно считать, что дорогу мы проходим моментально.
Например, в случае \(s=\)«rggry» и текущего света r возможны два варианта: либо зеленый свет наступит через через \(1\) секунду, либо через \(3\). Таким образом, ответ равен \(3\) — именно через столько секунд мы гарантированно сможем перейти дорогу, если текущий цвет r.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных уже сейчас горит зеленый цвет, поэтому можно перейти дорогу сразу же.
В третьем наборе входных данных если изначально горел красный цвет на второй секунде, то ждать зеленого цвета пришлось бы одну секунду, а если бы горел красный цвет на первой секунде, то уже две.
В четвертом наборе входных данных дольше всего ждать зеленый цвет мы будем с пятой секунды.