Palindrome

Do you know that The Chef has a special interest in palindromes? Yes he does! Almost all of the dishes in his restaurant is named by a palindrome strings. The problem is that a name of a dish should not be too long, so The Chef has only limited choices when naming a new dish. For the given positive integer N, your task is to calculate the number of palindrome strings of length not exceeding N, th