题目描述

把一个长度为 $len$ 的字符串围成一个圈，然后以任意一个字符作为起点，都会产生一个长度为 $len$ 的字符串。这些字符串中字典序最小的那个，称为原字符串的最小表示。

例如字符串 alabala，围成圈后可以得到以下 7 个字符串：

labalaa
abalaal
balaala
alaalab
laalaba
aalabal

其中字典序最小的是 aalabal，它的第一个字母在原字符串中的位置是 $6$（位置从 $0$ 开始计数）。

现在给定一个字符串，请你找出其最小表示的第一个字母在原字符串中的位置。如果有多个最小表示，输出第一个字母在原字符串中位置最小的那个。

输入格式

第一行一个整数 $t$，表示有 $t$ 组测试数据。

接下来 $t$ 行，每行首先是一个整数 $l$，表示原字符串的长度，然后是一个字符串，表示原字符串。字符串中只包含小写字母。

输出格式

对于每组测试数据，输出一行一个整数，表示该字符串最小表示的第一个字母在原字符串中的位置（从 $0$ 开始）。

样例

2
6 baabaa
7 alabala

1
6

样例解释：

• 第一组：字符串 baabaa 的最小表示为 aabaab，起始字符 a 在原字符串中的位置是 $1$。
• 第二组：字符串 alabala 的最小表示为 aalabal，起始字符 a 在原字符串中的位置是 $6$。

数据范围与提示

• $5 \le l \le 100000$
• 字符串仅包含小写字母
• 位置从 $0$ 开始计数

来源

CodesOnline