International Programming Contest
April 19, 2003, Blagoevgrad, Bulgaria
Sponsored by 
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 1st 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 Ј D1, D2,… ,Dn Ј 3 - numbers of the pegs which each of the disks is placed on
Input
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 D1, D2, ..., Dn, separated with single spaces. Tests are separated from each other by one empty line.
Output
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".
Sample Input
1
3
3 3 1
Sample Output
3