题目描述

小$\tt Z$ 是一名星际探险家，需要穿越一个由恒星组成的特殊星域。这个星域可以用一个字符串 $s = s_1 s_2 \ldots s_n$ 表示，其中每个字符代表一颗恒星的类型：

• L 表示左旋恒星（只能向左跃迁）；
• R 表示右旋恒星（只能向右跃迁）；

小$\tt Z$ 从星域起点（位置 $0$）出发，目标是到达星域终点（位置 $n+1$）。当小$\tt Z$ 位于某颗恒星 $i$（$1 \le i \le n$）时：

• 如果这是左旋恒星（L），小$\tt Z$ 只能向左跃迁；
• 如果这是右旋恒星（R），小$\tt Z$ 只能向右跃迁；

从起点出发时，小$\tt Z$ 只能向右跃迁。

在开始探险前，小$\tt Z$ 需要设定飞船的跃迁距离 $d$（之后不可更改）。每次跃迁时：

• 如果当前是左旋恒星，你可以跃迁到 $[\max(0, i-d), i-1]$ 范围内的任意恒星；
• 如果当前是右旋恒星，你可以跃迁到 $[i+1, \min(n+1, i+d)]$ 范围内的任意恒星；

小$\tt Z$ 可以重复访问同一颗恒星，并且可以进行任意多次跃迁。

你的任务是帮助小$\tt Z$ 找到最小的跃迁距离 $d$，确保能够从起点成功到达终点。题目保证总是存在这样的跃迁方案。

输入格式

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

接下来 $t$ 行，每行描述一个星域的恒星分布（由 L 和 R 组成的字符串）。

约束：所有测试用例的字符串总长度不超过 $2 \times 10^5$。

输出格式

对于每个测试星域，输出一行，包含一个整数，表示需要的最小跃迁距离 $d$。

输入输出样例

6
LRLLR
R
L
RL
LLR
RRRLLLRRR

3
1
2
2
3
4

样例 $\tt \#1$说明

2
RRRR
LLLL

1
5