I. iChandu
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

iChandu is a playful young man. He like strings a lot and has an interesting problem for you. He gives a string of lowercase letters of length N. You have to replace exactly one position in the string by character , such that the number of distinct palindromic substrings in the new string is maximized. You also have to find the number of different such strings possible.

Input

First line contains T(1 ≤ T ≤ 5), the number of test cases. Each test case consist of one line, the string iChandu gave you. Length of the string is N(1 ≤ N ≤ 105).

Output

For each test case output two values: maximum number of distinct palindromic substrings in the new string and different number of such strings possible.

Example
Input
1
aba
Output
3 3
Note

Sample test case 1:

Three different strings possible:

distinct palindromic substrings  = 3 .

distinct palindromic substrings = 3 .

distinct palindromic substrings = 3 .

Hence maximum distinct palindromic substrings are 3, and count of distinct strings that generate 3 different substrings is 3.