Mr Fraschetti gave a lot of math homework one day. EgorGor is sad, so he emails Mr Fraschetti asking him which pizza to eat hoping for a friendly mark boost. As a result, Mr Fraschetti gives EgorGor a math question about pizzas. He cries to himself dying, starving, desperate to impress Mr Fraschetti with his math skillz. Unfortunately, he has none. Help EgorGor solve the problem before he dies!

The Email goes as follows.

Hello EgorGor, I'm glad you asked me about pizzas!

Pizza is delicious, but so are juicy math problems. There are three plates; a giant paper plate ~A~, a white ceramic plate ~B~, and a golden porcelain Italian plate ~C~. On the paper plate, there is a stack of ~N~ pizzas numbered ~1~ to ~N~ each smaller than the one below it. Your job is to place all the pizzas on the beautiful Italian plate ~C~ in the same descending order. Be careful, my gourmet pizzas are to be moved one at a time, only the pizza at the top of a stack can be moved, and no larger pizza should be placed on top of a smaller one or else it'll destroy all the pizzas below it. You may use any plate as a temporary place to store the pizzas. Follow these rules using the most efficient solution, and I might spare your worthless soul.

~ Mr. Fraschetti

N.B. Would you bet ten bucks?

Save EgorGor by determining the shortest amount of moves it takes to move Mr Fraschetti's pizzas.

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

On the first line, output in an integer the least amount of moves it takes to get all the pizzas on place ~C~.

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.

Output in the format pizza plate1 - plate2.

Subtask 1 [20%]

~1 \le N \le 3~

Subtask 2 [80%]

~1 \le N \le 15~

Sample Input

2

Sample Output

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

Explanation

First, you place the smallest pizza and put in on plate ~B~, place the largest pizza on plate ~C~, then finally move the smallest pizza from plate ~B~ to ~C~.