Mirko and Slavko have a new board game. The game board resembles a complete infinite binary tree. More precisely, the board consists of nodes and two-way roads connecting them. The root node is located at the
top of the board and we say it is at level zero. Each node has exactly two children, the left child and the
right child , located in the lower-left and the lower-right directions of the parent node. The level of a
child node is one greater than the level of the parent node. In addition to roads connecting a parent node with its children, there are roads connecting all of the nodes at a particular level – for each level, starting from the leftmost node, there is a road connecting each node to the next node to the right on the same level.
Figure 1: The second test example below
Each path through the game board is a sequence of steps, each moving from a node to a different node via
a single road. Each step can be described by a single character as follows:
· character „1