Maximal Distinct Palindromic Substrings via Rotation

P has learned a new method for string manipulation called rotation.

A rotation is defined as follows: remove the last character of the original string and place it at the beginning to form a new string.

P can perform this rotation operation any number of times. His goal is to achieve a new string which contains as many essentially distinct palindromic substrings as possible. Two palindromes are considered essentially different if either their lengths differ or there exists some position where the characters differ.

You are given a string S. By applying the rotation operations (i.e. selecting any cyclic shift of S), help P to achieve his goal and output the maximum number of essentially distinct palindromic substrings that can appear in the resulting string.

Note: A palindrome is a string that reads the same forward and backward. All formulas, if any, must be written in LaTeX format.

inputFormat

The input consists of a single line containing the string S.

Constraints: The length of S is at least 1. You may assume S is composed of lowercase English letters.

outputFormat

Output a single integer, representing the maximum number of essentially distinct palindromic substrings among all cyclic rotations of S.

sample

a

1