Spokes Wheel

Interview

Time limit1sMemory limit256 MB

Summary

Find the fewest left or right rotations that turn the first 32-spoke binary pattern into the second, or report that it is impossible.

Level: Easy3 of 10
Topics: Bit manipulation, Brute force
Solved: No attempts yet

Problem

A 32-spoke wheel has each spoke tagged 0 or 1. Given hex states before and after rotation, find the minimum number of left or right rotations that transforms the first state into the second.

Input

Test count $T$ , then each line has two 32-bit hex values $N_1$ and $N_2$ .

Output

Print Case #X: Y Left, Y Right, Y Any, or Not possible.

Examples3

Example 1

Input

4
80000000 1
1 80000000
AAAAAAAA 55555555
1 7

Expected output

Case #1: 1 Left
Case #2: 1 Right
Case #3: 1 Any
Case #4: Not possible

Example 2
Input
```
1
80000000 80000000
```
Expected output
```
Case #1: 0 Any
```
Example 3
Input
```
1
1 1
```
Expected output
```
Case #1: 0 Any
```