Problem D
Doom's Day
Input: Standard
Input
Output: Standard
Output
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 3^n * 3^m 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.
|
1 |
2 |
3 |
to |
1 |
10 |
19 |
|
4 |
5 |
6 |
2 |
11 |
20 |
|
|
7 |
8 |
9 |
3 |
12 |
21 |
|
|
10 |
11 |
12 |
4 |
13 |
22 |
|
|
13 |
14 |
15 |
5 |
14 |
23 |
|
|
16 |
17 |
18 |
6 |
15 |
24 |
|
|
19 |
20 |
21 |
7 |
16 |
25 |
|
|
22 |
23 |
24 |
8 |
17 |
26 |
|
|
25 |
26 |
27 |
9 |
18 |
27 |
|
1 |
2 |
3 |
to |
1 |
4 |
7 |
|
4 |
5 |
6 |
2 |
5 |
8 |
|
|
7 |
8 |
9 |
3 |
6 |
9 |
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 ≤ 10^9 and n≤ 10^9.
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 Output
for Sample Input
|
5 1 1 1 2 3 1 2 2 98876767 12234 |
Case 1: 2 Case 2: 3 Case 3: 4 Case 4: 2 Case 5: 98889001 |
Problemsetter: Tanaeem Md. Moosa
Special Thanks to: Jane Alam Jan