Alyosha splits into non-palindromic factors. On some days Alyosha feels like he is tired, so he just split a string in minimal number of palindromes.
In other days Alyosha is full of energy and he splits a string in maximal amount of palindromes. There is an option to split a string in one piece that means to leave it as it was. Can you determine how much factors will have Alyosha depending on his mood?
The only line contains a string of n English letters (1 ≤ n ≤ 2 · 105).
If there is no way to cut this string into non-palindromes, output “-1”.
Otherwise output the minimal and maximal amount of non-palindromes in splitting.
A palindrome is a string which equals its reversal. A non-palindrome is a string that is not a palindrome. For example, “abacaba” is a palindrome, а “abcde” is a non-palindrome.
Problem Author: Nikita Sivukhin
Problem Source: Palindromic Contest, July 11, 2015