Слева от строки \(s = s_1 s_2 \ldots s_n\), состоящей из \(n\) символов, находится лягушка (точнее, изначально лягушка находится в клетке \(0\)). Каждый символ строки \(s\) — это или 'L', или 'R'. Это значит, что если лягушка находится в \(i\)-й клетке и \(i\)-й символ — это 'L', то она может прыгать только влево. Если лягушка стоит в \(i\)-й клетке и \(i\)-й символ — это 'R', то она может прыгать только вправо. Из клетки \(0\) лягушка может прыгать только вправо.
Заметим, что лягушка может прыгать в одну и ту же клетку дважды и может совершить столько прыжков, сколько ей потребуется.
Лягушка хочет достичь \(n+1\)-й клетки. Лягушка выбирает некоторое целое положительное значение \(d\) перед самым первым прыжком (и потом не может изменить его) и прыгает не более, чем на \(d\) клеток за раз. То есть, если \(i\)-й символ — 'L', то лягушка может прыгнуть в любую клетку из отрезка \([max(0, i - d); i - 1]\), а если \(i\)-й символ — 'R', то лягушка может прыгнуть в любую клетку из отрезка \([i + 1; min(n + 1; i + d)]\).
Лягушка не хочет прыгать слишком далеко, поэтому ваша задача — найти минимальное возможное значение \(d\), при котором лягушка сможет достичь клетки \(n+1\) из клетки \(0\), если будет прыгать не более, чем на \(d\) клеток за раз. Гарантируется, что всегда возможно достичь \(n+1\) из \(0\).
Вам нужно ответить на \(t\) независимых наборов входных данных.
Выходные данные
Для каждого набора входных данных выведите ответ — минимальное возможное значение \(d\), при котором лягушка может достичь клетки \(n+1\) из клетки \(0\), если будет совершать прыжки длиной не более, чем \(d\).
Примечание
Картинка, описывающая первый набор тестовых данных из примера и один из возможных ответов:
Во втором наборе тестовых данных из примера лягушка может прыгнуть только напрямую из \(0\) в \(n+1\).
В третьем наборе тестовых данных лягушка может выбрать \(d=3\), прыгнуть в клетку \(3\) из клетки \(0\) и затем прыгнуть в клетку \(4\) из клетки \(3\).
В четвертом наборе тестовых данных из примера лягушка может выбрать \(d=1\) и прыгнуть \(5\) раз вправо.
В пятом наборе тестовых данных из примера лягушка может прыгнуть только напрямую из \(0\) в \(n+1\).
В шестом наборе тестовых данных из примера лягушка может выбрать \(d=1\) и прыгнуть \(2\) раза вправо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
LRLRRLL
L
LLR
RRRR
LLLLLL
R
|
3
2
3
1
7
1
|