402825: GYM100889 I iChandu

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. iChandutime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExampleInput
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.

加入题单

上一题 下一题 算法标签: