题目描述

给定一个长度为 $n$ 的仅包含小写字母的字符串 $s$ （下标从 $1$ 开始编号），请求出任意一对 $(l,r)$ （ $1\le l\le r\le n$ ），满足 $s$ 在翻转区间 $[l,r]$ 后是一个回文串。

换言之，你需要保证 $s_1s_2\ldots s_{l-1}s_rs_{r-1}\ldots s_{l+1}s_ls_{r+1}\ldots s_{n-1}s_n$ 和 $s_ns_{n-1}\ldots s_{r+1}s_ls_{l+1}\ldots s_{r-1}s_rs_{l-1}\ldots s_{2}s_1$ 这两个字符串相等。

输入格式

本题包含多组数据。

第一行输入一个整数 $t$ ，表示数据组数。接下来描述 $t$ 组数据。

对于每组数据，输入两行：

第一行包含一个整数 $n$ ，表示字符串 $s$ 的长度。

第二行即为字符串 $s$ 。

输出格式

对于每组数据，输出一行两个整数 $l$ 和 $r$ ，表示你所构造的区间为 $[l,r]$ 。若无解则输出 $-1\ -1$ 。

数据范围

对于 $100\%$ 的数据， $1 \le t \le 100$ ， $1 \le n \le 10^5$ ， $\sum{n} \le 2 \times 10^6$ （即所有字符串的长度之和不超过 $2 \times 10^6$ ）。

本题共包含 $20$ 个测试点，各测试点的具体限制如下表所示：

特殊性质：对于每个字符串 $s$ ，存在一种字符 $c$ ，满足 $c$ 在 $s$ 中出现了恰好一次（不同的 $s$ 可能对应不同的 $c$ ）。

输入样例 1

3
5
bcbaa
4
abcb
6
acbacb

输出样例 1

1 4
-1 -1
4 6

输入样例 2

2
6
lysine
17
yukinoshihsyukino

输出样例 2

-1 -1
1 6

样例解释

样例 $1$ 中，

对于第一组数据，$\underline{\texttt{bcba}}\texttt{a} \to \underline{\texttt{abcb}}\texttt{a}$，故 $[1,4]$ 是一个满足题意的区间。

对于第二组数据， 容易发现 $\texttt{abcb}$ 无论如何都不能构成回文串。

对于第三组数据，$\texttt{acb}\underline{\texttt{acb}} \to \texttt{acb}\underline{\texttt{bca}}$，故 $[4,6]$ 是一个满足题意的区间。值得一提的是，$[1,3]$ 同样也是一个符合题意的区间。