1267: Palindrome

Time Limit: 1 Sec  Memory Limit: 128 MB
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.

Sample Input Copy


Sample Output Copy

1 5 
9 10