题目描述

我们定义一个字符串$S$的最小表示法为,$S[i...n]+S[1...i-1]$的字典序最小，比如字符串$"bac"$的最小表示法为$"acb"$，本题请返回最小表示法的位置。保证不数据随机。

输入格式

一个数t表示有t组数据 之后是t行，有t行字符串

输出格式

输出$i$

样例

无

数据范围与提示

t<=100

len(s)=1000000