I Wanna Be A Palindrome

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给出一个字符串,仅由小写字母组成。请找出是否仅删除其中的一个字母之后,
字符串变成回文串。

Input

 输入第一行是一个整数 T,表示有 T 组数据。
每组数据占一行,每行包含一个非空字符串,字符串长度不超过 10 5 。

Output

 对于每组测试数据,输出一行包含一个整数 K ,表示删除字符串中第 K 个字
母后字符串变成回文串。若有多个这样的整数 K 存在,则输出其中最小的一个
整数。如果输入的字符串原本就是一个回文串,或者找不到这样的整数,则输出
"No Solution" (不包含引号)。

Sample Input

3
aaab
abab
abcba

Sample Output

4
1
No Solution

Hint

 

Source

Ningbo_2014_Contest