Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

E. Бот для игры: Камень-ножницы-бумага
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

«Камень-ножницы-бумага» — это игра для двух игроков. Игра состоит из раундов. В каждом раунде каждый игрок выбирает один из трех ходов: камень, бумага или ножницы. В зависимости от выбранных ходов происходит следующее:

  • если один игрок выбрал камень, а другой игрок выбрал бумагу, выигрывает игрок, выбравший бумагу, и получает одно очко;
  • если один игрок выбрал ножницы, а другой игрок выбрал бумагу, выигрывает игрок, выбравший ножницы, и получает одно очко;
  • если один игрок выбрал ножницы, а другой игрок выбрал камень, выигрывает игрок, выбравший камень, и получает одно очко;
  • если оба игрока выбрали один и тот же ход, никто не выигрывает и никто не получает очко.

Монокарп решил сыграть против бота. В ходе игры Монокарп заметил, что поведение бота очень предсказуемо, а именно:

  • в первом раунде он выбирает камень;
  • в каждом раунде, кроме первого, он выбирает тот ход, который выигрывает у хода оппонента в предыдущем раунде (например, если в предыдущем раунде его оппонент сыграл ножницы, то сейчас бот выберет камень).

У Монокарпа есть любимая строка s, состоящая из символов R, P и/или S. Монокарп решил сыграть серию раундов против бота. Однако он хочет, чтобы выполнялись оба следующих условия:

  • итоговый счет был в пользу Монокарпа (то есть количество раундов, которые он выиграл, было строго больше, чем количество раундов, которые выиграл бот);
  • в последовательности ходов бота (где R обозначает камень, P обозначает бумагу, а S — ножницы) строка s встречалась как непрерывная подстрока.

Помогите Монокарпу и посчитайте минимальное количество раундов, которое ему необходимо сыграть против бота, чтобы удовлетворить оба вышеописанных условия.

Входные данные

Первая строка содержит одно целое число t (1t104) — количество наборов входных данных.

Единственная строка каждого набора содержит строку s (1|s|2105), состоящая из символов R, P и/или S.

Дополнительное ограничение на входные данные: сумма длин строк s по всем наборам входных данных не превосходит 2105.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество раундов, которое необходимо сыграть Монокарпу против бота, чтобы удовлетворить оба вышеописанных условия.

Пример
Входные данные
7
SS
R
RPS
RPPP
SPPRSP
PPP
PR
Выходные данные
3
1
3
6
7
5
3
Примечание

В первом примере Монокарп может сыграть 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 в пользу Монокарпа.