Uolevi recently created a new programming language. The programming language has only the following three functions for manipulating strings:

new (c) - takes a character c and creates a string that consists of a single character c.

expand (S, c) - takes a string S and a character c and creates the string ScS.

reverse (S) - reverses the string S.

Your task is to find out if a given string could have been created using Uolevi's programming language.

Input

The only line of input contains one string of length n. The string consists of lowercase english letters.

Output

Output 10-4 if the string could have been created by Uolevi's programming language and QAQ otherwise.

Constraints

• 1 \le n \le 2000

Examples

Input:

abacaba

Output:

10-4

Input:

uolevi

Output:

QAQ