All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Divyam is teaching his student Amit about palindromes. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. For example, the string “abcba” is a palindrome. After teaching about it, Divyam gave a puzzle for Amit to solve:
Given a string S. Find the number of positions in S where we can insert a character to convert it into a palindrome. Character can be inserted in the beginning or the end, so there will be (N+1) possible positions for the insertion in a string having original length N. For example, if S = “aaa”, then there are four positions where we can insert a character so that the converted string is a palindrome. Converted palindromes are “aaaa”, “aaaa”, “aaaa” and “aaaa”. Inserted character is shown in boldface.
Amit finds the puzzle too difficult. Can you help him in solving it?
- First line of input contains an integer T denoting the number of test cases.
- First line of each test case will contain a string S containing lowercase letters only.
OutputPrint T lines, each containing an integer: the solution for the corresponding test case.
Subtask #1: 20 points
- 1 ≤ T ≤ 5, 1 ≤ length of string ≤ 1000
Subtask #2: 80 points
- 1 ≤ T ≤ 5, 1 ≤ length of string ≤ 105
Input: 2 aaa aca Output: 4 2
First sample has been explained in the problem statement.
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.