{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eExiste um sapo à esquerda da string $$$s \u003d s_1 s_2 \\ldots s_n$$$ que consiste em $$$n$$$ caracteres (para ser mais preciso, o sapo inicialmente está na célula $$$0$$$). Cada caractere de $$$s$$$ é ou \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eL\u003c/span\u003e\u0027 ou \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eR\u003c/span\u003e\u0027. Isso significa que se o sapo está na célula $$$i$$$ e o caractere na posição $$$i$$$ é \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eL\u003c/span\u003e\u0027, o sapo só pode pular para a esquerda. Se o sapo está na célula $$$i$$$ e o caractere na posição $$$i$$$ é \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eR\u003c/span\u003e\u0027, o sapo só pode pular para a direita. \u003cspan class\u003d\"tex-font-style-bf\"\u003eO sapo só pode pular para a direita a partir da célula $$$0$$$\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eNote que o sapo pode pular para a mesma célula duas vezes e pode realizar quantos pulos forem necessários\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eO sapo deseja alcançar a célula $$$n+1$$$. O sapo escolhe um valor \u003cspan class\u003d\"tex-font-style-bf\"\u003einteiro positivo\u003c/span\u003e $$$d$$$ \u003cspan class\u003d\"tex-font-style-bf\"\u003eantes do primeiro pulo\u003c/span\u003e (e não pode alterá-lo posteriormente) e pula no máximo $$$d$$$ células de uma vez. Ou seja, se o caractere na posição $$$i$$$ é \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eL\u003c/span\u003e\u0027, então o sapo pode pular para qualquer célula em um intervalo de $$$[max(0, i - d); i - 1]$$$, e se o caractere na posição $$$i$$$ é \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eR\u003c/span\u003e\u0027, então o sapo pode pular para qualquer célula em um intervalo de $$$[i + 1; min(n + 1; i + d)]$$$.\u003c/p\u003e\u003cp\u003eO sapo não quer pular muito longe, então sua tarefa é encontrar o valor mínimo possível de $$$d$$$ para que o sapo possa alcançar a célula $$$n+1$$$ a partir da célula $$$0$$$ se ele pode pular no máximo $$$d$$$ células de uma vez. \u003cspan class\u003d\"tex-font-style-bf\"\u003eÉ garantido que sempre é possível alcançar $$$n+1$$$ a partir de $$$0$$$\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eVocê deve responder a $$$t$$$ casos de teste independentes.\u003c/p\u003e"}},{"title":"Entrada","value":{"format":"HTML","content":"\u003cp\u003eA primeira linha da entrada contém um inteiro $$$t$$$ ($$$1 \\le t \\le 10^4$$$) — o número de casos de teste.\u003c/p\u003e\u003cp\u003eAs próximas $$$t$$$ linhas descrevem os casos de teste. O $$$i$$$-ésimo caso de teste é descrito como uma string $$$s$$$ consistindo de pelo menos $$$1$$$ e no máximo $$$2 \\cdot 10^5$$$ caracteres \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eL\u003c/span\u003e\u0027 e \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eR\u003c/span\u003e\u0027.\u003c/p\u003e\u003cp\u003eÉ garantido que a soma dos comprimentos das strings em todos os casos de teste não excede $$$2 \\cdot 10^5$$$ ($$$\\sum |s| \\le 2 \\cdot 10^5$$$).\u003c/p\u003e"}},{"title":"Saída","value":{"format":"HTML","content":"\u003cp\u003ePara cada caso de teste, imprima a resposta — o valor mínimo possível de $$$d$$$ para que o sapo possa alcançar a célula $$$n+1$$$ a partir da célula $$$0$$$ se ele pular no máximo $$$d$$$ de uma vez.\u003c/p\u003e"}},{"title":"Exemplos","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\nLRLRRLL\nL\nLLR\nRRRR\nLLLLLL\nR\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n3\n1\n7\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Observação","value":{"format":"HTML","content":"\u003cp\u003eA imagem descrevendo o primeiro caso de teste do exemplo e uma das respostas possíveis:\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/82e72044207a7f5055c1cc150d3699b1?v\u003d1713612504\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eNo segundo caso de teste do exemplo, o sapo só pode pular diretamente de $$$0$$$ para $$$n+1$$$.\u003c/p\u003e\u003cp\u003eNo terceiro caso de teste do exemplo, o sapo pode escolher $$$d\u003d3$$$, pular para a célula $$$3$$$ a partir da célula $$$0$$$ e depois para a célula $$$4$$$ a partir da célula $$$3$$$.\u003c/p\u003e\u003cp\u003eNo quarto caso de teste do exemplo, o sapo pode escolher $$$d\u003d1$$$ e pular $$$5$$$ vezes para a direita.\u003c/p\u003e\u003cp\u003eNo quinto caso de teste do exemplo, o sapo só pode pular diretamente de $$$0$$$ para $$$n+1$$$.\u003c/p\u003e\u003cp\u003eNo sexto caso de teste do exemplo, o sapo pode escolher $$$d\u003d1$$$ e pular $$$2$$$ vezes para a direita.\u003c/p\u003e"}}]}