Adam 刚刚学会走路（在他的兄弟 Omar 的帮助下），但他经常摔倒。为了保持平衡，他会把手举在空中（这是真的），一旦他把手放下，他就会摔倒。

给定一个字符串，每个字符代表他走的一步。如果字符是 'U'，意味着这一步他的手是举在空中的；如果字符是 'D'，意味着他的手是放下的，他会在这一步摔倒。你的任务是计算他在第一次摔倒前会走多少步。

输入格式

程序将测试一个或多个测试用例。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例包含一个非空字符串，长度最多为 100 个字符，每个字符要么是 'U'，要么是 'D'。字符从左到右代表 Adam 走路的顺序。

输出格式

对于每个测试用例，输出一行，包含 Adam 在摔倒前会走的步数；如果他不会摔倒，则输出字符串的长度。

样例

输入 1

3
UUUDU
DDD
UU

输出 1

3
0
2

说明

在第一个测试用例中，他在走了 3 步后摔倒。

在第二个测试用例中，他在迈出任何步子之前就摔倒了。

在第三个测试用例中，他根本没有摔倒。