题目描述

字母项链是由一串 \(A = a_1,a_2,...,a_m\) 序列组成，\(m\) 表示制成项链的珠子的个数。当项链围成一圈时，最后一个字母 \(a_m\) 就是 \(a_1\) 的前驱（前一个）。第 \(i\) 个珠子比第 \(j\) 个珠子更容易断裂就是说序列 \(a_i.a_{i+1},...,a_n.a_1,....,a_{i-1}\) 的字典序小于序列 \(a_j,a_{j+1},...,a_n,a_1,...,a_j-1\) 的字典序。序列 \(a_1,a_2,...,a_n\) 的字典序小于序列 \(b_1,b_2,...,b_n\) 的字典序就是存在一个整数 \(i(i≤n)\), 对于每个 \(j(1≤j < i)\) 都要有 \(a_j=b_j\) 且 \(a_i < b_i\)。编程找出最容易断裂的地方。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(m（10≤m≤10000）\)，表示组成项链的字母长度，第二行为组成项链的字母序，每个珠子由一个英语的小写字母表示 \(（a-z）\)。

输出格式

对于每组数据，输出项链最坏连接处字母珠子的编号 \(i\)，表示 \(A[i]\) 就是 \(n\) 个可能断裂点的字典序最小的地方。如果有不止一个的解，输出最小的 \(i\)。

样例1

输入样例1

2
11
amandamanda 20
afdaksdjfoijaakjlkpq

输出样例1

11
13

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T2\)

文件IO

freopen("necklace.in","r",stdin);
freopen("necklace.out","w",stdout);