对决

题目描述

有 $n$ 个人排成一个发言序列，每个人属于 L 队或 R 队。轮到当前序列最前面的 $x$ 发言时，他可以指定另一个仍在序列中的人 $y$ 退出；$y$ 退出后，$x$ 移到序列末尾。重复此过程，直到序列中剩下的人全部属于同一队，则该队获胜。双方均采取最优策略。

给定 $T$ 个初始序列，请判断每个序列的获胜队伍。

输入格式

第一行一个正整数 $T$。

接下来 $T$ 行，每行一个仅由 L 和 R 组成的字符串，表示一个发言序列。

输出格式

输出 $T$ 行，每行一个字符 L 或 R，表示获胜的一方。

样例

输入

3
LLR
RLLRRLLL
LLRRRR

输出

L
L
R

数据范围

• 对于 20% 的数据，字符串总长度不超过 $10$；
• 对于 40% 的数据，字符串总长度不超过 $10^3$；
• 对于 100% 的数据，字符串总长度不超过 $10^6$。