飞车狂飙

Problem Description

你现在正在筹备一场飞车比赛，众所周知，飞车比赛会同时有多辆车进行，因此赛道的设计十分关键。 现在你要修建由 $n$ 个赛道段组成的赛道，赛道会被铺设在一个无限大的二维平面网格上，每个赛道段占一个单元格。 一条合法的赛道需要满足如下条件： 赛道不能重叠，也就是相同的单元格上不能放置多个赛道段，因为重叠会使得赛车之间发生碰撞的概率提升。 赛道必须成环，因为飞车比赛的起终点是在同一点。 你现在让一位工人在平面上某个单元格的一条边上就位，并按照你给的预命令来进行修建赛道。预命令是一个长度为 $n$ 的仅包含 $\texttt{LRS}$ 的字符串，其中 $\texttt{L}$ 表示在他面向的单元格铺设一段相对于他面向的方向左转 $90$ 度的赛道，$\texttt{R}$ 表示在他面向的单元格铺设一段相对于他面向的方向右转 $90$ 度的赛道，$\texttt{S}$ 表示在他面向的单元格铺设一段相对于他面向的方向直行的赛道。之后，工人会顺着赛道来到下一条边上。 但你无法从你下达的预命令来看出赛道是否合法。现在你需要想办法判断它是否合法从而来指挥工人修建赛道。

Input

第一行一个整数 $T$（$1\le T\le 10^4$），表示测试数据组数。 对于每组数据，第一行一个整数 $n$（$1\le n\le 10^5$），表示轨道长度。第二行一个长为 $n$ 且仅由 $\texttt{L}$，$\texttt{S}$，$\texttt{R}$ 三种字符组成的字符串。 保证对于所有数据，满足 $\sum n\le 10^6$。

Output

对于每组数据，输出一个整数表示该字符串对应的预命令是否合法。 如果轨道存在重叠，输出 $-1$；如果轨道无重叠，但不成环，输出 $0$；如果轨道无重叠且成环，输出 $1$。

Sample Input

4
1
S
4
RRRR
10
LSLSLSSLSL
18
LSSLSLSLSSSRSRSSRR

Sample Output

0
1
0
-1

Hint

样例中四条赛道如下图所示。其中蓝色线为初始时工人所在边，箭头朝向为初始时工人面向的方向。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（6）