A tragedy has occured, and EgorGor has died because he could not solve Fraschetti's Pizza. EgorGor's successor Serog1sPerog1s has come to avenge him and beat Fraschetti's pizza problem. The original problem was too easy for Serog1sPerog1s so Mr Fraschetti decided to up the game and make the problem more difficult. If you haven't solved Fraschetti's Pizza, solve it before proceeding with this one.

Greetings Serog1sPerog1s, welcome to the pizza dungeon!

EgorGor died last time, unable to figure out the way of the pizza, but I feel the pizza spirits strong within you! A curse has dawned on the plates when EgorGor failed last time, and now the initial plate ~A~ is possessed. The same rules as the previous problem remain, with the addition of this new rule. Now, no pizza can be moved directly from the initial plate ~A~ to the final plate ~C~ or vice versa, but has to come from the middle plate ~B~. Figure out the most efficient moves to move my stack of pizzas, or suffer the same fate as EgorGor.

~ Mr. Fraschetti

N.B. Do you have ten bucks?

Help Serog1sPerog1s by determining the shortest moves to move Mr Fraschetti's pizzas.

N.B. Solving the original pizza stacks problem will probably help

Input Specification

The first line of input will contain an integer ~N~ ~(1 \le N \le 15)~, representing the number of pizzas.

Each case consists of the three plates, and the pizzas all start on the paper plate. It is guaranteed that the pizzas are stacked on top of each other in descending order, largest on the bottom and smallest on the top like a pyramid.

Output Specification

For each move, output the pizza that's being moved, the plate you're moving the pizza from, and the plate it will be placed on. If you move the same pizza consecutively, output the third plate it will be placed on.

Output in the format pizza# - plate1 - plate2 or pizza# - plate1 - plate2 - plate3 each variable separated by a dash.

Subtask 1 [20%]

~1 \le N \le 3~

Subtask 2 [80%]

~1 \le N \le 15~

Sample Input

2

Sample Output

1 - A - B - C
2 - A - B
1 - C - B - A
2 - B - C
1 - A - B - C

Explanation

Move pizza 1 from plate ~A~ to ~B~ and then to ~C~, then move pizza 2 from plate ~A~ to ~B~, move pizza 1 from plate ~C~ to ~B~ and then to ~A~, move pizza 2 from plate ~B~ to ~C~, and finally move pizza 1 from plate ~A~ to ~B~ and then to ~C~. This avoids moving a pizza from plate ~B~ to ~C~.