On Halloween, Quirrell suddenly enters the Great Hall and claims to have seen a troll in the dungeons. The evacuation of the students into their dormitories is started immediately. At the same time, a group of teachers prepares to search the dungeons for the troll.

The dungeons were constructed over a long period of time and are a system of connected corridors. They originally consisted of just one long corridor with an entrance and an exit. Over time, new corridors were added. Each new corridor had its entrance placed on the right-hand wall of an already existing corridor and ended in the same corridor where it started, but further towards the exit. Furthermore, a newly built corridor did only intersect with the corridor containing its entrance and exit. To ensure that nobody gets lost, each corridor contains markers pointing to the corridor's exit.

Illustration of the second sample.

The teachers have a map of the dungeons and want to use the fact that there is only one exit to their advantage. They lock the exit and start all together at the entrance to the system. To ensure that all of them actually reach the exit, they agree that each of them only moves towards the exit of the current corridor or enters another corridor through its entrance. Of course, they want to avoid that the troll can leave through the entrance or even attack them from behind. Hence, they want to move in such a way that there is never a path between the entrance of the dungeons and the troll which is not blocked by some teacher. Fortunately, each teacher is capable enough to deal with the troll, that is, it is sufficient if it can be guaranteed that at least one teacher encounters the troll. How many teachers have to go to the dungeons?

The system of corridors in the dungeons can also be constructed by composition of systems of corridors. For each such system there are two positions that are defined as the entrance and the exit of the corridor, respectively.

• () denotes just one corridor with an entrance and an exit.
• (A+B) denotes that we append the system B to A, that is, the entrance of A is the new entrance of the system, the exit of B is the new exit and we merge the exit of A with the entrance of B.
• (A*B) denotes that A and B are parallel to each other. This means that the entries of A and B are merged and form the new entrance and the exits of A and B are merged as well and form the new exit.