팰린드롬 만들기

문제 정보

문제

앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “anonona”를 만들 수도 있고, “a”를 붙여서 “anona”를 만들 수도 있지요. 물론 S를 뒤집은 문자열을 S 뒤에 붙이면 항상 팰린드롬이 되므로, 결과 팰린드롬이 가능한 한 짧았으면 합니다.

S가 주어질 때 S에서 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(<=50)가 주어집니다. 그 후 각 테스트 케이스마다 문자열 S가 주어집니다. 주어지는 문자열의 길이는 1 이상 10만 이하이며, 알파벳 소문자로만 구성됩니다.

출력

각 테스트 케이스마다 한 줄에 S를 이용해 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력합니다.

예제 입력

3
there
amanaplanacanal
xyz

예제 출력

7
21
5

노트

4개의 댓글이 있습니다.