AIBOHP - Aibohphobia


BuggyD suffers from AIBOHPHOBIA - the fear of Palindromes. A palindrome is a string that reads the same forward and backward.

To cure him of this fatal disease, doctors from all over the world discussed his fear and decided to expose him to large number of palindromes. To do this, they decided to play a game with BuggyD. The rules of the game are as follows:

BuggyD has to supply a string S. The doctors have to add or insert characters to the string to make it a palindrome. Characters can be inserted anywhere in the string.

The doctors took this game very lightly and just appended the reverse of S to the end of S, thus making it a palindrome. For example, if S = "fft", the doctors change the string to "ffttff".

Nowadays, BuggyD is cured of the disease (having been exposed to a large number of palindromes), but he still wants to continue the game by his rules. He now asks the doctors to insert the minimum number of characters needed to make S a palindrome. Help the doctors accomplish this task.

For instance, if S = "fft", the doctors should change the string to "tfft", adding only 1 character.

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

Each test case consists of one line, the string S. The length of S will be no more than 6100 characters, and S will contain no whitespace characters.

Output

For each test case output one line containing a single integer denoting the minimum number of characters that must be inserted into S to make it a palindrome.

Example

Input:
1
fft

Output:
1

hide comments
nitdgpdeb: 2019-06-19 10:58:55

Traceback (most recent call last):
File "./prog.py", line 35, in <module>
EOFError: EOF when reading a line
error occurs when I submit my solution.Not able to read the test case no.However on my ide my code is running fine.

Any suggestion please

toolatetostart: 2019-06-13 09:30:14

can be solved without lcs,just apply condition of pallindrome.don't forgot to declare string as char s[6102];cost me tle,use printf and scanf,size of dp[6102][6102]

saurav_paul: 2019-05-29 12:29:02

Accepted in one go. Easily can solve using LCS, but how to solve without LCS?

tarusus: 2019-05-20 19:06:58

HELP..............
how can I solve it without using LCS.
Recursion give TLE.

ankityadav: 2019-03-27 12:23:50

1-it can be solved without LCS
2-simple dp
3-consider only first and last character
4-pass string as reference

akibk001: 2019-03-26 20:42:56

check 1 length string too..
2
f
a

ans should be
0
0

problem_solved: 2019-01-29 14:02:53

AC without LCS, just always consider the first and the last letters. Good luck.

naduhrin78: 2019-01-11 00:36:07

@cypher33 Number of insertions = length of non-palindromic subsequence. You can find longest palindromic subsequence using lcs of the reverse of string. Figure rest out.

Last edit: 2019-01-11 00:36:26
cypher33: 2019-01-09 15:43:27

@md_meraj1319 can u explain why this formula works?

md_meraj1319: 2018-12-26 06:46:38

mayank_75 (length_of_given_string)-lcs(given_string,reverse_of_given_string)


Added by:Matthew Reeder
Date:2006-10-29
Time limit:1.940s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006