Problem1267--Palindrome

1267: Palindrome

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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.

Input

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.

Output

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.

Sample Input Copy

1 
abcdcxxxba 

Sample Output Copy

7 
1 5 
9 10