Longest Palindrome Construction

Marcus loves word games. In this problem, you are given a string s consisting of uppercase and lowercase English letters. Your task is to compute the length of the longest palindrome that can be constructed using the letters of s. A palindrome is a word that reads the same backward as forward. Note that the solution is case sensitive.

Formally, given a string \( s \) with \( 1 \leq |s| \leq 1000 \), determine the maximum length \( L \) of a palindrome that can be formed using some or all of the letters of s.

inputFormat

A single line containing the string s.

outputFormat

Output a single integer representing the length of the longest palindrome that can be constructed from the given string.## sample

abccccdd

7