** **

**Task F. Hanoi tower**

"Hanoi tower" puzzle is well known. There are 3 pegs with
numbers: #1, #2 and #3. *N* disks of different diameters are set on the 1^{st}
peg in the following order: the lower disk is set, the larger diameter it has.
Your aim is to move all disks onto the second peg using the peg #3 as an
auxiliary one. Following the rules within a move it's allowed to replace only
one uppermost disk. Besides it's forbidden to put a disk of bigger diameter
onto a disk of smaller one.

Distribution of disks on the pegs during the game must be assigned
as sequence *D* (element #i of the sequence is equal to the number of peg
where the disk #i is placed on). For instance, game status after the third move
is apparently determined by sequence *D*=(3, 3, 1) (the first and the
second disks are set on the third peg and the third disk is on the peg #1).

*Example*. Let's assume that 3 disks are set on the peg #1. Then the movement
of the disks can be depicted in the following table (disks are numbered in
ascending order of diameters):

Point of move |
Peg #1 disks |
Peg #2 disks |
Peg #3 disks |
sequence D |

0 |
1, 2, 3 |
- |
- |
1, 1, 1 |

1 |
2, 3 |
1 |
- |
2, 1, 1 |

2 |
3 |
1 |
2 |
2, 3, 1 |

3 |
3 |
- |
1, 2 |
3, 3, 1 |

4 |
- |
3 |
1, 2 |
3, 3, 2 |

5 |
1 |
3 |
2 |
1, 3, 2 |

6 |
1 |
2, 3 |
- |
1, 2, 2 |

7 |
- |
1, 2, 3 |
- |
2, 2, 2 |

Your aim is to write a program **F.EXE** either to determine (using arbitrary sequence *D*) the number
of moves from the beginning of the game to the given position on condition of
performing the optimal algorithm; or to print "-1" in the case of
incorrect sequence declaration (i.e. the given position cannot be achieved performing
the optimal algorithm).

*Reference notes*. Optimal algorithm can be specified with the following recursive
procedure.

` `

` `

` `

`procedure Hanoi(N:integer; From, To_, Temp : integer);`

` Begin`

` if N>0 then`

` begin`

` Hanoi(N-1, From, Temp, To_);`

` writeln (N, From, To_);`

` Hanoi(N-1, Temp, To_, From)`

` end`

`End;`

For example, to move 5 disks it's enough to call Hanoi (5,1,2,3)

*Admonition*. It is obvious that during the game process simultaneous setting of
disks on all the pegs (#1, #2, #3) is never repeated, thus the answer will
always be unequivocal.

**Limitations**

1 Ј *n*<64 - quantity of disks

1 Ј**
***D _{1},
D_{2},… ,D_{n}*

The first line of input contains integer *m*
– the number of the tests, each with two lines. On the first of the two lines
is written the integer *n*. The second line contains integers *D*_{1},
*D*_{2}, ..., *D*_{n}, separated with single spaces.
Tests are separated from each other by one empty line.

Output file has to contain *m* lines – one
for each test. At the line there is either the quantity (number) of moves, or
the constant "-1".

`1`

`3`

`3 3 1`

` `

`3`