A maze can have multiple solution paths from start to finish.  In this example you can see that there are two distinct solutions that do not cross the same position twice.

Given a maze, find the longest path from start to finish that does not cross the same position twice.  If there is no solution, return zero.

Note that the maze dimensions will be small enough that you can store it with unsigned 32-bit integers.

Input

Each maze is defined as follows:

1. A row begins with a coordinate pair (X,Y).
2. After the coordinate pair, between zero-to-four coordinates are listed.  This defines the connected paths from the initial coordinate and the following coordinate(s).
3. Optionally, the line may end with an "s" or "e".
   • 's' signifies the starting square for the maze.
   • 'e' signifies the ending square for the maze.

Output

The length of the longest path through the maze that does not cross the same position twice.  You should count the start and end positions.

Example

Input:
(1,1),(1,2)(2,1)
(2,1),(1,1)(2,2)(1,3)e
(3,1),(2,1)(4,1)
(4,1),(3,1)(4,2)
(1,2),(1,1)(1,3)
(2,2),(2,1)
(3,2),(4,2)(3,3)
(4,2),(4,1)(3,2)
(1,3),(1,2)(1,4)
(2,3),(2,4)
(3,3),(3,2)(4,3)
(4,3),(3,3)(4,4)
(1,4),(1,3)(1,5)(2,4)
(2,4),(1,4)(2,3)(2,5)(3,4)
(3,4),(2,4)(4,4)
(4,4),(4,3)(3,4)(4,5)
(1,5),(1,4)
(2,5),(2,4)s
(3,5),(4,5)
(4,5),(3,5)(4,4)

Output:
11