A. Зал славы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Талия — легендарный гроссмейстер в шахматах. У нее есть $$$n$$$ кубков, расположеных в ряд, кубки пронумерованы от $$$1$$$ до $$$n$$$ (слева направо), и по одной лампе рядом с каждым из кубков (лампы пронумерованы так же, как и кубки).

Каждая лампа направлена либо налево, либо направо; лампа освещает все кубки в заданном направлении (но не освещает кубок, рядом с которым стоит). Формально, у Талии есть строка $$$s$$$ из символов «L» и «R», описывающая направления ламп. Лампа номер $$$i$$$ освещает:

  • кубки $$$1,2,\ldots, i-1$$$, если $$$s_i$$$ это «L»;
  • кубки $$$i+1,i+2,\ldots, n$$$, если $$$s_i$$$ это «R».

Талия может выполнить следующую операцию не более одного раза:

  • Выбрать индекс $$$i$$$ ($$$1 \leq i < n$$$);
  • Поменять местами лампы $$$i$$$ и $$$i+1$$$ (не меняя их направление). Другими словами, поменять $$$s_i$$$ и $$$s_{i+1}$$$.

Талия попросила вас осветить все кубки (то есть сделать так, чтобы каждый кубок был освещен хотя бы одной лампой), или сообщить, что это невозможно сделать. Если это можно сделать, вы можете выполнить одну операцию или ничего не делать. Обратите внимание, что нельзя менять направления освещения ламп, можно только поменять местами соседние лампы.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит положительное целое число $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — количество кубков.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую только из букв «L» и «R»: $$$i$$$-я буква описывает направление $$$i$$$-й лампы.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$100\,000$$$.

Выходные данные

Для каждого набора входных данных выведите $$$-1$$$, если невозможно осветить все кубки, выполнив одну операцию или ничего не делая. Иначе выведите $$$0$$$, если операцию выполнять не надо (т. е. все кубки освещены при изначальном положении ламп), или индекс $$$i$$$ ($$$1 \leq i < n$$$), если нужно поменять местами лампы $$$i$$$ и $$$i+1$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
6
2
LL
2
LR
2
RL
2
RR
7
LLRLLLR
7
RRLRRRL
Выходные данные
-1
1
0
-1
3
6
Примечание

В первом примере можно поменять местами лампы $$$1$$$ и $$$2$$$ или ничего не делать. В любом случае мы получим строку «LL». Не все кубки будут освещены, так как кубок $$$2$$$ не освещен ни одной лампой: лампа $$$1$$$ ничего не освещает, а лампа $$$2$$$ освещает только кубок $$$1$$$.

Во втором примере необходимо поменять местами лампы $$$1$$$ и $$$2$$$. Строка станет равной «RL«. Кубок $$$1$$$ освещен лампой $$$2$$$, а кубок $$$2$$$ освещен лампой $$$1$$$, поэтому можно подсветить все кубки.

В третьем примере все кубки изначально освещены, поэтому не выполнять операцию является корректным решением.

В последних двух примерах не обязательно менять местами лампы, так как все кубки изначально освещены. Однако представленные решения тоже верные.