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.