We all know about the legend oftower 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 verifiedby 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 stepthe puzzle is rearranged by reading it in row major order and putting them incollumn major order. See the following examples.

Now every day the puzzle is rearrangedonce. The legend says if someday initial configuration returns the world willend. Now you are wondering when the world is going to end.

Input

Input starts with a linecontaining number of test cases T ≤ 10000. Each test case containstwo positive integerm ≤  10^9and n≤ 10^9.

Output

For each case print one linecontaining days before dooms day. The input will be such that this number fitsin 64 bit unsigned integer.

SampleInput                                                 Outputfor Sample Input

Problemsetter:Tanaeem Md. Moosa

SpecialThanks to: Jane Alam Jan

题意：往3^n * 3^m的格子里1到3^(n+m) 的数，每次的操作是：将数按行优先拿出来，再按列优先放进去，求多少次后回到初始状态

思路：规律ans=(a+b)/gcd(a, b);

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	int t, a, b, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &a, &b);	
		printf("Case %d: %d\n", cas++, (a+b)/gcd(a, b));
	}
	return 0;
}

UVA - 11774 Doom's Day （规律）