#PL. Palindrome Lover

    ID: 3766 远端评测题 500ms 1536MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute-forcepalindrome-5pattern-12string-39basic-7

Palindrome Lover

Asad is a 10 years old boy. He loves to learn new logic from computer science. Palindrome is an interesting topic to him. So, He starts practicing to finding palindrome in his everyday life.

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward. such as – madam, 0001000 etc.

He faces a problem and asks for your help. You are a great programmer in our country.Now, you have given a string S . You have to do a permutation of string S through many times (can be 0 times) such that you will get a palindromic string P . You have to check whether it is possible to form a palindrome after any permutation or not.

Input

Every line of the input contains a single string S .

Constraints:

  • S will consist only of lowercase English letters (i.e. characters 'a' through 'z').
  • 1 ≤ |S| ≤ 105

Output

For each test case, print a single line. Print 1, if it is possible to find at least one valid permutation P of string S which is a palindrome. Otherwise print -1.

Example

Input:
abc
abab
Output:
-1
 1

Note:

In, Case 2: ‘baab’ is a valid permutations of string ‘abab’ which is also a palindrome. So output will be 1.