MSUBSTR - Mirror Strings !!!

no tags 

As we all know Utkarsh is very good at solving number based problems, this time Arpit thinks smartly and gives Utkarsh to solve a problem on Strings. Arpit gives Utkarsh a string and challenges him to find the length of largest substring that have its mirror string same as its original one and number of such substrings. Now Utkarsh is busy at preparing Avishkar papers so he asks you to help him in doing this task.

E.g. for mirror string: Consider string "lalit" then its mirror string will be "tilal".

Input

There are t numbers of test cases (t <= 200) followed t lines where each line contains a character string of lower case characters (a-z) of length l (1 <= l <= 3000).

Output

There will be two integers per line separated by space indicating the length of largest substring which have its mirror string same and number of such substrings.

Example

Input:
3
lalit
abedcdetr
abcde

Output:
3 1
5 1
1 5

hide comments
utpal kumar jha: 2013-12-25 16:24:27

finallyy :D :D

satya hemanth: 2013-11-06 10:15:50

century!!

tuhin: 2013-06-12 18:05:58

@problemsetter please avoid spoilers .
@Pradeep mathesh please dont make it obvious

Last edit: 2013-07-12 04:56:52
Tushar Makkar (Retired): 2013-03-13 12:34:30

Time limit is too strict for Python 2.7 .That is why there is no accepted solution in python. Even O(n) code giving TLE ....
P.S : Thanks Pradeep Mathesh for giving hint.

Last edit: 2013-03-13 12:34:50
Jose Luis Castrillon Garrido: 2012-10-26 20:32:02

this problem is wrong, please fix it.

Swapnil R.Mehta: 2012-09-24 11:32:05

Getting WA.
Pls check id=7714234.
Checked almost all the cases which can be framed.

(Tjandra Satria Gunawan)(曾毅昆): 2012-09-23 17:06:43

Oops, My 'unknown complexity' algo is got AC in 0.01s.

Last edit: 2012-09-23 17:06:36
Rahul Dubey: 2013-02-09 09:03:54

@praveen123 O(n^2) with little optimization is getting accepted ..

praveen123: 2012-09-23 09:24:33

O(n*n) not getting accepted, is there any other better algorithm, Please give just a hint , yes or no!

Last edit: 2012-09-22 23:00:24

Added by:! include(L.ppt)
Date:2012-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MNNIT OPC 21-09-2012