说明

时间限制：1 Sec 内存限制：256 MB 输入文件：string.in 输出文件：string.out

小明有一个长度为 $n$ 的全部由小写字母字符串 $s$。他可以对 $s$ 做这样的修改：

1. 选择一个整数 $k$ 满足 $1 \le k \le n$
2. 选择从 $1$ 到 $k$ 的子串进行反转，再选择 $2$ 到 $k+1$ 的子串进行反转，再选择 $3$ 到 $k+2$ 的子串进行反转，以此类推，直到选择 $n-k+1$ 到 $n$ 的子串进行反转。

比如说，字符串 $s$ 是 xiaoming，$k=4$，以下为 $s$ 被修改的过程：

• xiaoming（原字符串）
• oaixming（旋转了第一个长度为 $4$ 的子串）
• omxiaing（旋转了第二个长度为 $4$ 的子串）
• omiaixng（旋转了第三个长度为 $4$ 的子串）
• ominxiag（旋转了第四个长度为 $4$ 的子串）
• omingaix（旋转了最后一个长度为 $4$ 的子串）

所以，$s$ 经过 $k=2$ 的一系列变化后最终会变成 omingaix。

小明希望选择一个 $k$，使得经过上述变化的字符串字典序最小。如果多个不同的 $k$ 都能满足要求，他想要取最小的一个。请你写个程序来实现目标。

一个字符串 $a$ 比 $b$ 字典序更小需要一下条件中只有一个满足：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在从左往右 $a$ 和 $b$ 的第一个不同的位置，$a$ 上的字符在字母表中比 $b$ 上字符更靠前。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 行，第 $i$ 行为第 $i$ 组询问，为一个全部由小写字母组成的字符串 $s$。

输出格式

$t$ 组输出，第 $i$ 组输出对应于第 $i$ 组询问。

每组询问包含两行：

第一行为一个字符串，表示可以通过修改得到的字典序最小的字符串 $s'$。

第二行为一个整数，为与之相应的 $k$。如果多个 $k$ 都可以达到字典序最小的字符串，输出其中最小的那个。

样例

样例 1

6
abab
qwerty
aaaaa
alaska
lfpbavjsm
p

abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1

数据范围

令 $|s|$ 表示字符串 $s$ 的长度。

对 $40\%$ 的数据，满足 $1 \le |s| \le 200$

对 $100\%$ 的数据，满足 $1 \le t \le 10$，$1 \le |s| \le 5000$