403878: GYM101350 I Mirrored String II
Description
Note: this is a harder version of Mirrored string I.
The gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for them to discover is mirrored strings.
A mirrored string is a palindrome string that will not change if you view it on a mirror.
Examples of mirrored strings are "MOM", "IOI" or "HUH". Therefore, mirrored strings must contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y} and be a palindrome.
e.g. IWWI, MHHM are mirrored strings, while IWIW, TFC are not.
A palindrome is a string that is read the same forwards and backwards.
Given a string S of length N, help the gorillas by printing the length of the longest mirrored substring that can be made from string S.
A substring is a (possibly empty) string of characters that is contained in another string S. e.g. "Hell" is a substring of "Hello".
InputThe first line of input is T – the number of test cases.
Each test case contains a non-empty string S of maximum length 1000. The string contains only uppercase English letters.
OutputFor each test case, output on a line a single integer - the length of the longest mirrored substring that can be made from string S.
ExampleInput3Output
IOIKIOOI
ROQ
WOWMAN
4
1
3