TOHMOVE1 - Tower of Hanoi Movement - Easy

no tags 

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
  3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2N − 1, where n is the number of disks.

The description is retrieved from Wikipedia


From the description above, AVM wants to know the ath step of optimal solution. The set of Tower of Hanoi consists of N disks and 3 rods (A as the source rod, B as the spare rod, and C as the target rod).

Input

The input file consists of several lines. The first line contains a single number T representing the number of test cases. The next T lines contains N and a representing the number of disk and the ath move.

Output

The output file should contains T lines. The i-th line should contain P : A => C , the Pth disk, the rod of Pth disk before the movement, and the rod of Pth disk after the movement.

Constraint

1 <= T <= 100
1 <= N <= 20
1 <= a <= 2N - 1

Example

Input:
3
2 3
3 5
3 7

Output:
1 : B => C
1 : B => A
1 : A => C

Explanation

The 2-disks Tower of Hanoi optimal solution is:
1 : A => B
2 : A => C
1 : B => C
Therefore, the first test case answer is
1 : B => C
The 3-disks Tower of Hanoi optimal solution is:
1 : A => C
2 : A => B
1 : C => B
3 : A => C
1 : B => A
2 : B => C
1 : A => C
Therefore, the second test case answer is
1 : B => A
and the last test case answer is
1 : A => C

hide comments
wisfaq: 2018-03-06 15:33:26

Nice problem


Added by:AVM
Date:2018-03-02
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All