Submit: 0 Solved: 0

[Submit] [Status] [Web Board] [Creator:]

You are given a string `S`. You task is to find two strings `A` and `B` such that:

`A`and`B`are two non-overlapping substrings of`S`.`A`appears befores`B`in`S`.- String
`A`+ B is a palindrome and |`A`+`B`| is maximal possible.

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains a string `S` (1 ≤ |`S`| ≤ 100000). The string consists of lowercase English letters only.

For each test case, output an integer denoting the maximum value of |`A`+`B`| on the first line.

On the second and the third lines, print two numbers denoting 1-indexed positions of the first and the last characters of substrings `A` and `B` in string `S`. If one of the substrings is empty, output "-1 -1" for its positions. If there are several possible answers, print any one of them.

```
1
abcdcxxxba
```

```
7
1 5
9 10
```