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.


-----Input-----

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$).


-----Output-----

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.


-----Example-----
Input
6
LRLRRLL
L
LLR
RRRR
LLLLLL
R

Output
3
2
3
1
7
1



-----Note-----

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

[Image]

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.

Difficulty: introductory

Starter code:

Solutions:
for i in range(int(input())):
    s='R' + input() + 'R'
    prev=0
    ma=-1
    for i in range(1,len(s)):
        if s[i]=='R':
            ma=max(ma,i-prev)
            prev=i
    print(ma)        
        


#!/usr/bin/env python3
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    s = input().rstrip() + "#"
    max_l = 0
    seq_l = 0
    for ch in s:
        if ch == "L":
            seq_l += 1
        else:
            max_l = max(max_l, seq_l)
            seq_l = 0
    print(max_l + 1)

def main():
    import sys
    input = sys.stdin.readline

    for _ in range(int(input())):
        S = input().rstrip('\n')
        cnt = 0
        ans = 1
        for s in S:
            if s == 'L':
                cnt += 1
                ans = max(ans, cnt+1)
            else:
                cnt = 0
        print(ans)


def __starting_point():
    main()

__starting_point()

from bisect import bisect_left, bisect_right


def go():
    # n = int(input())
    # a = list(map(int, input().split()))
    s= input()
    prev=-1
    mx=0
    for i, aa in enumerate(s):
        if aa=='R':
            mx=max(mx,i-prev)
            prev=i
    return max(mx,len(s)-prev)

t = int(input())
for _ in range(t):
    print(go())


t = int(input())
for i in range(t):
    s = input() + "R"
    mx = -float('inf')
    cur = 0
    while s.find('R', cur) != -1:
        nxt = s.find('R', cur)
        d = nxt - cur
        if d > mx:
            mx = d
        cur = nxt + 1
    print(mx + 1)


t = int(input())
while t!=0:
    t-=1
    s=input()
    pos = 0
    ans = 0
    for i in range(len(s)):
        if s[i] == 'R':
            ans = max(ans, i-pos+1)
            pos = i+1
    ans = max(ans, len(s)+1-pos)
    print(ans)


from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import functools 
import sys
import bisect
import string
import math
import time
import random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

t=I()
for _ in range(t):
    s=input()+'R'
    ans=1
    c=1
    for i in s:
        if i=='L':
            c+=1
        else:
            ans=max(ans,c)
            c=1
    print(ans)




from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

for _ in range(val()):
    s = st()
    n = len(s)
    l = [0 for i in range(n + 2)]
    d = -1
    last = n + 1
    # print(s)
    for i in range(len(s),0,-1):
        if s[i-1] == 'R':
            l[i] = last - i
            last = i
            d = max(d,l[i])
    d = max(d,last - 0)
    print(d if d > 0 else n + 1)
        


import sys
input = sys.stdin.readline
from collections import Counter

t=int(input())
for tests in range(t):
    S=input().strip()

    NOW=0
    ANS=0
    for s in S:
        if s=="L":
            NOW+=1
        else:
            ANS=max(ANS,NOW)
            NOW=0
    ANS=max(ANS,NOW)
    print(ANS+1)



t = int(input())

for loop in range(t):

    s = input()

    ans = 0

    now = 0
    for i in s:

        if i == "R":
            now = 0
        else:
            now += 1
            ans = max(ans,now)

    print(ans + 1)


def one():
    return int(input())


def more():
    return list(map(int, input().split()))


for _ in range(one()):
    s = input() + 'R'
    cur = 0
    mx = -1
    for ind, i in enumerate(s):
        if i == 'R':
            d = ind + 1 - cur
            mx = max(mx, d)
            cur = ind + 1

    print(mx)


t = int(input())
while(t):
    t -= 1
    a = input()
    n = len(a)
    inds = [-1]
    for i in range(n):
        if(a[i] == 'R'):
            inds.append(i)
    inds.append(n)
    ans = 0
    for i in range(1, len(inds)):
        ans = max(ans, inds[i]-inds[i-1])
    print(ans)

q = int(input())
for i in range(q):
    s = list(input()) + ['R']
    ans = 0
    cur = 0
    for x in s:
        if x == 'L': cur += 1
        else:
            if ans < cur: ans = cur
            cur = 0
    print(ans + 1)

import sys
input = sys.stdin.readline

Q = int(input())
Query = [list(input().rstrip()) for _ in range(Q)]


for S in Query:
    tmp = 0
    ans = 0
    for i, s in enumerate(S):
        if s == "L":
            tmp += 1
        else:
            ans = max(tmp+1, ans)
            tmp = 0
    ans = max(tmp+1, ans)
    print(ans)

import sys

input = sys.stdin.readline

q = int(input())

for _ in range(q):
    S = 'R' + input().rstrip() + 'R'
    ans = -1
    prv = 0
    for i in range(1, len(S)):
        if S[i] == 'R':
            diff = i - prv
            ans = max(ans, diff)
            prv = i
    print(ans)

t=int(input())
while t:
    s=input()
    ans=0
    temp=0
    for i in range(len(s)):
        if(s[i]=='L'):
            temp+=1
        else:
            ans=max(ans,temp+1)
            temp=0
    ans=max(ans,temp+1)  
    print(ans)
    t-=1

 
import sys
input=sys.stdin.readline
for j in range(int(input())):
    a = input()
    a = a + 'R'
    ans = 1
    count =0
    for j in a:
        if(j=='L'):
            count= count + 1
        else:
            count = count + 1
            if(count>ans):
                ans = count
            count = 0
    print(ans)
            


def run_length_compress(string):
    string = string + "@"
    n = len(string)
    begin = 0
    end = 1
    cnt = 1
    ans = []
    while True:
        if end >= n:
            break
        if string[begin] == string[end]:
            end += 1
            cnt += 1
        else:
            ans.append((cnt, string[begin]))
            begin = end
            end = begin + 1
            cnt = 1

    return ans

  
import sys
input = sys.stdin.readline


t = int(input())
for i in range(t):
    s = input()
    s = run_length_compress(s[0:-1])
    ans = 1
    for num, char in s:
        if char == "L":
            ans = max(num + 1, ans)
    print(ans)