Symmetric Strings

A non-empty string S is called symmetric if it is the concatenation of another string W with itself, that is, when S = WW. Additionally, we say that string W is half of S. For example, the string "hellohello" is symmetric (and its half is the string "hello"), whereas the strings "abca" and "abcab" are not symmetric. Obviously, the lengths of symmetric strings are even numbers (twice the length of their respective halves).

Consider a string S whose length is an odd number. It is required to determine whether a single character can be removed from S so that the resulting string is symmetric. Furthermore, it is required to find out if this can be done in a unique way or if different removals can result in more symmetric strings.

Problem:

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads some such strings and for each one does one of the following:

• If removing one character results in a unique symmetric string, it should print half of that string.
• If removing one character can result in multiple different symmetric strings, it should print the number (code) 1.
• If removing any character does not result in a symmetric string, it should print the number (code) 0.

Input Files:

The input file named symstr.in is a text file with the following structure. The first line contains two integers T and N, separated by a single space. The number T represents the number of strings to follow, while N is an odd number representing the length of each string. Each of the next T lines contains a string consisting of N uppercase Latin alphabet letters.

Output Files:

The output file named symstr.out is a text file with the following structure. It consists of exactly T lines, where each line contains the answer for the corresponding input string (as described above).

Examples of Input - Output Files:

STDIN (symstr.in)

4 9
ABCKDABCD
ABCDEFGHI
ABABABABA
AAAAAAAAA

STDOUT (symstr.out)

ABCD
0
1
AAAA

Explanation: In the example, there are 4 strings, each with 9 letters. For each string, the answer is explained below:

• From the string "ABCKDABCD", if the letter "K" is removed, then the symmetric string "ABCDABCD" is obtained, half of which is "ABCD" — this is the unique symmetric string that can result from removing one character.
• From the string "ABCKDABCD", no matter which letter is removed, a symmetric string does not result, so "0" (zero) is printed.
• From the string "ABABABABA", if the first "A" is removed, then the symmetric string "BABABABA" is obtained, while if the last "A" is removed, then the symmetric string "ABABABAB" is obtained. Therefore, removing one character does not result in a unique symmetric string, so "1" (one) is printed.
• From the string "AAAAAAAAA", no matter which letter is removed, the symmetric string "AAAAAAAA" is obtained, half of which is "AAAA".

Constraints:

• For test cases worth 50%, of the total points, it will be:
  1 ~\le~ Τ ~\le~ 10, 3 ~\le~ Ν ~\le~ 10.000 and N will be an odd number
• • For test cases worth 70%, of the total points, you won't need to print the code "1" (one) — uniqueness check is not required
• • For test cases worth 100%, of the total points, it will be:
    1 ~\le~ Τ ~\le~ 10, 3 ~\le~ Ν ~\le~ 1.000.000 and N will be an odd number

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: symstr *)

for PASCAL coders

/* USER: username
LANG: C
TASK: symstr */

for C coders

/* USER: username
LANG: C++
TASK: symstr */

for C++ coders

/* USER: username
LANG: Java
TASK: symstr */

for Java coders

# USER: username
# LANG: Python
# TASK: symstr

for Python coders