Misha and Palindrome Degree

CodeForces - 504C