SA-IS后缀数组

小Q最近阅读了SA-IS算法在线性时间内构造后缀数组的相关论文，面对任何字符串题，都可以想出线性时间的算法。

小T在经历过二分图匹配事件后，再也不相信小Q所说的话。面对小Q，小T又给出了一道字符串题：

给定一个长度为$n$的小写字符串$S[1..n]$，设$suf_i$表示以$i$ 为开始的后缀，即$S[i..n]$。

记$|X|$为字符串$X$的长度，对于两个字符串$X$和$Y$，定义$X$的字典序比$Y$小，当且仅当存在非负整数$k(k\leq \min(|X|,|Y|))$使得$X$的前$k$个字符与$Y$的前 $k$个字符对应相同，并且要么满足$|X| = k$且$|Y| > k$，要么满足$k < \min(|X|,|Y|)$且$X$的第$k+1$个字符比$Y$的第$k+1$个字符小。例如aa的字典序比aaa小，ab的字典序比ba小。

请对每个$i(1\leq i<n)$，判断$suf_i$和$suf_{i+1}$的字典序大小关系。

只会吹牛的小Q又不会做了，所以他再一次向你紧急求助。请写一个程序，判断相邻两个后缀的大小关系。

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组数据第一行包含一个正整数$n(2\leq n\leq 1000000)$，表示字符串$S$的长度。

第二行包含一个长度为$n$的小写字符串$S$。

对于每组数据，输出一行$n-1$个字符，第$i$个字符表示$suf_i$和$suf_{i+1}$的大小关系，若$suf_i<suf_{i+1}$，输出$<$，否则输出$>$，显然不存在相等关系。

1
17
quailtyacmbestacm

<><<<<><<><<<><<

"字节跳动杯"2018中国大学生程序设计竞赛-女生专场