We all know about the legend of tower of Hanoi. It is said that the world will end after finishing the puzzle. What we don’t know is another legend about when the world will end which is verified by the scientists. It is all about a 3n ∗ 3m grid. Initially the grid is filled with 1 to 3(m+n) in row major order. At each step the puzzle is rearranged by reading it in row major order and putting them in collumn major order. See the following examples. 123 456 789 101112 13 14 15 161718 192021 222324 252627 to 11019 21120 31221 41322 5 14 23 61524 71625 81726 91827 123 147 4 5 6 to 2 5 8 789 369 Now every day the puzzle is rearranged once. The legend says if someday initial configuration returns the world will end. Now you are wondering when the world is going to end. Input Input starts with a line containing number of test cases T ≤ 10000. Each test case contains two positive integer m ≤ 109 and n ≤ 109. Output For each case print one line containing days before dooms day. The input will be such that this number fits in 64 bit unsigned integer. Sample Input 5 11 12 31 22 98876767 12234 Sample Output Case 1: 2 Case 2: 3
2/2 Case 3: 4 Case 4: 2 Case 5: 98889001