CF1324C.Frog Jumps

There is a frog staying to the left of the string $s = s_1 s_2 \ldots s_n$ consisting of $n$ characters (to be more precise, the frog initially stays at the cell $0$). Each character of $s$ is either 'L' or 'R'. It means that if the frog is staying at the $i$-th cell and the $i$-th character is 'L', the frog can jump only to the left. If the frog is staying at the $i$-th cell and the $i$-th character is 'R', the frog can jump only to the right. The frog can jump only to the right from the cell $0$.

Note that the frog can jump into the same cell twice and can perform as many jumps as it needs.

The frog wants to reach the $n+1$-th cell. The frog chooses some positive integer value $d$ before the first jump (and cannot change it later) and jumps by no more than $d$ cells at once. I.e. if the $i$-th character is 'L' then the frog can jump to any cell in a range $[max(0, i - d); i - 1]$, and if the $i$-th character is 'R' then the frog can jump to any cell in a range $[i + 1; min(n + 1; i + d)]$.

The frog doesn't want to jump far, so your task is to find the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it can jump by no more than $d$ cells at once. It is guaranteed that it is always possible to reach $n+1$ from $0$.

You have to answer $t$ independent test cases.

有一只青蛙位于由 $n$ 个字符组成的字符串 $s = s_1 s_2 \ldots s_n$ 的左侧（更准确地说，青蛙初始时位于第 $0$ 号单元格）。字符串 $s$ 的每个字符均为 'L' 或 'R'。其含义如下：若青蛙当前位于第 $i$ 号单元格，且第 $i$ 个字符为 'L'，则青蛙只能向左跳跃；若第 $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$，使得青蛙能从第 $0$ 号单元格出发，在每次跳跃距离不超过 $d$ 的前提下，最终到达第 $n+1$ 号单元格。题目保证从第 $0$ 号单元格总能到达第 $n+1$ 号单元格。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The next $t$ lines describe test cases. The $i$-th test case is described as a string $s$ consisting of at least $1$ and at most $2 \cdot 10^5$ characters 'L' and 'R'.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $2 \cdot 10^5$ ($\sum |s| \le 2 \cdot 10^5$).

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来的 $t$ 行描述各个测试用例。第 $i$ 个测试用例由一个字符串 $s$ 描述，该字符串仅由字符 'L' 和 'R' 组成，长度至少为 $1$，至多为 $2 \cdot 10^5$。

保证所有测试用例的字符串长度之和不超过 $2 \cdot 10^5$（即 $\sum |s| \le 2 \cdot 10^5$）。

For each test case, print the answer — the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it jumps by no more than $d$ at once.

对于每个测试用例，输出答案——即青蛙从单元格 $0$ 出发、每次跳跃距离不超过 $d$ 的前提下，能够到达单元格 $n+1$ 的最小可能的 $d$ 值。

The picture describing the first test case of the example and one of the possible answers:

In the second test case of the example, the frog can only jump directly from $0$ to $n+1$.

In the third test case of the example, the frog can choose $d=3$, jump to the cell $3$ from the cell $0$ and then to the cell $4$ from the cell $3$.

In the fourth test case of the example, the frog can choose $d=1$ and jump $5$ times to the right.

In the fifth test case of the example, the frog can only jump directly from $0$ to $n+1$.

In the sixth test case of the example, the frog can choose $d=1$ and jump $2$ times to the right.

描述示例中第一个测试用例的图片及其中一种可能的答案：

在示例的第二个测试用例中，青蛙只能直接从 $0$ 跳到 $n+1$。

在示例的第三个测试用例中，青蛙可以选择 $d=3$，先从单元格 $0$ 跳到单元格 $3$，再从单元格 $3$ 跳到单元格 $4$。

在示例的第四个测试用例中，青蛙可以选择 $d=1$，并向右连续跳跃 $5$ 次。

在示例的第五个测试用例中，青蛙只能直接从 $0$ 跳到 $n+1$。

在示例的第六个测试用例中，青蛙可以选择 $d=1$，并向右连续跳跃 $2$ 次。