«Камень-ножницы-бумага» — это игра для двух игроков. Игра состоит из раундов. В каждом раунде каждый игрок выбирает один из трех ходов: камень, бумага или ножницы. В зависимости от выбранных ходов происходит следующее:
- если один игрок выбрал камень, а другой игрок выбрал бумагу, выигрывает игрок, выбравший бумагу, и получает одно очко;
- если один игрок выбрал ножницы, а другой игрок выбрал бумагу, выигрывает игрок, выбравший ножницы, и получает одно очко;
- если один игрок выбрал ножницы, а другой игрок выбрал камень, выигрывает игрок, выбравший камень, и получает одно очко;
- если оба игрока выбрали один и тот же ход, никто не выигрывает и никто не получает очко.
Монокарп решил сыграть против бота. В ходе игры Монокарп заметил, что поведение бота очень предсказуемо, а именно:
- в первом раунде он выбирает камень;
- в каждом раунде, кроме первого, он выбирает тот ход, который выигрывает у хода оппонента в предыдущем раунде (например, если в предыдущем раунде его оппонент сыграл ножницы, то сейчас бот выберет камень).
У Монокарпа есть любимая строка \(s\), состоящая из символов R, P и/или S. Монокарп решил сыграть серию раундов против бота. Однако он хочет, чтобы выполнялись оба следующих условия:
- итоговый счет был в пользу Монокарпа (то есть количество раундов, которые он выиграл, было строго больше, чем количество раундов, которые выиграл бот);
- в последовательности ходов бота (где R обозначает камень, P обозначает бумагу, а S — ножницы) строка \(s\) встречалась как непрерывная подстрока.
Помогите Монокарпу и посчитайте минимальное количество раундов, которое ему необходимо сыграть против бота, чтобы удовлетворить оба вышеописанных условия.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество раундов, которое необходимо сыграть Монокарпу против бота, чтобы удовлетворить оба вышеописанных условия.
Примечание
В первом примере Монокарп может сыграть PPR, тогда ходы бота будут RSS, и счет будет \(2:1\) в пользу Монокарпа.
Во втором примере Монокарп может сыграть P, тогда ход бота будет R, и счет будет \(1:0\) в пользу Монокарпа.
В третьем примере Монокарп может сыграть RPR, тогда ходы бота будут RPS, и счет будет \(1:0\) в пользу Монокарпа.
В четвертом примере Монокарп может сыграть RRRSPR, тогда ходы бота будут RPPPRS, и счет будет \(3:2\) в пользу Монокарпа.
В пятом примере Монокарп может сыграть PRRSPRS, тогда ходы бота будут RSPPRSP, и счет будет \(6:1\) в пользу Монокарпа.
В шестом примере Монокарп может сыграть PRRRS, тогда ходы бота будут RSPPP, и счет будет \(3:2\) в пользу Монокарпа.
В седьмом примере Монокарп может сыграть RSR, тогда ходы бота будут RPR, и счет будет \(1:0\) в пользу Монокарпа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
SS
R
RPS
RPPP
SPPRSP
PPP
PR
|
3
1
3
6
7
5
3
|