Omega Switching Network

Omega Switching Network is a very useful tool using in UMA Multiprocessors System. Next is about how The Omega Switching Network works in UMA Multiprocessors System.
As we know that the UMA Multiprocessors System is a MIMD(multipl-instructions and multi-data) computer, it has multiple CPUs and multiple Memories. To make the problem simple and easy, let's consider only one condition - N CPUs and N Memories (N is a power of 2). So we need log₂N stages, with N/2 switches each, for a total of (N/2)log₂N switches, illustrated in Figure 2.

Figure 1. The perfect shuffle	Figure 2. An omega switching network

The wiring pattern of the omega switching network is often called the perfect shuffle, since the mixing of the signals at each stage resembles a deck of cards being cut in half and then mixed card-for-card, which can also be described using the formula:
δ(x_n-1, x_n-2 ... x₁, x₀) = x_n-2, x_n-3 ... x₁, x₀, x_n-1 ( x_i = 0 or 1, i = [0, n-1]) So for N=8, the perfect shuffle would be Figure 1. Using this pattern, the omega switching network for N=8 would be Figure 2.
To see how the omega network works, suppose that CPU 011 wants to read a word from memory module 110. The CPU sends a READ message to switch 4A containing 110 in the Module field. The switch takes the first(i.e., leftmost) bit of 110 and uses it for routing. A 0 routes to the upper output and a 1 routes to the lower one. Since this bit is a 1, the message is routed via the lower output to 4B.
All the second-stage switches ,including 4B, use the second bit for routing. This is also a 1, so the message is now forwarded via the lower output to 4C. Here the third bit is tested and found to be a 0. Consequently, the message goes out on the upper output and arrives at memory 110, as desired. The path followed by this message is marked in Figure 2 by the letter a.
Now you task is to a random N omega switching network (N=2^k , 1 ≤ k ≤ 26), you should output the signal paths between given CPU and Memory in the UMA.
Input
The first line of input is a number M (1 ≤M ≤100), indicating the number of test cases. For each test case, the first line contains two numbers N and S. N is the number of CPUs and Memories. Then S lines follow, each line gives two number i and j, respectively represent the ith CPU sends signals to jth Memory.
Output
For each test case, you should first output a line "Case t:", where t is the case number. Then S lines, output the signal path between given CPUs and Memories. The output format of each path is given in the Sample Output without tailing hyphen. Output a blank line after each test case.
Sample Input

1
8 4
3 6
4 0
0 7
1 1

Sample Output

Case 1:
4A-4B-4C
1A-1B-1C
1A-2B-4C
2A-3B-1C

Hint
1. The CPUs and Memories always be marked from 0 to N-1.
2. For each ith (1 ≤ i ≤ log₂N ) stage, the switches will be marked with 1a,2a,3a...(N/2)a, where a is the ith letter counting from 'A' to 'Z'.