402825: GYM100889 I iChandu

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.

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 ≤ 10⁵).

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

1
aba

3 3

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.