Two people play the following string game. Initially the players have got some string s. The players move in turns, the player who cannot make a move loses.

Before the game began, the string is written on a piece of paper, one letter per cell.

An example of the initial situation at s = "abacaba"

A player's move is the sequence of actions:

1. The player chooses one of the available pieces of paper with some string written on it. Let's denote it is t. Note that initially, only one piece of paper is available.
2. The player chooses in the string t=t₁t₂... t_|t| character in position i (1≤i≤|t|) such that for some positive integer l (0<i-l;i+l≤|t|) the following equations hold: t_i-1=t_i+1, t_i-2=t_i+2, ..., t_i-l=t_i+l.
3. Player cuts the cell with the chosen character. As a result of the operation, he gets three new pieces of paper, the first one will contain string t₁t₂... t_i-1, the second one will contain a string consisting of a single character t_i, the third one contains string t_i+1t_i+2... t_|t|.

An example of making action (i=4) with string s = «abacaba»

Your task is to determine the winner provided that both players play optimally well. If the first player wins, find the position of character that is optimal to cut in his first move. If there are multiple positions, print the minimal possible one.