Problem Description

Xiaoben has a binary function $f(a,b)$.

If $a<2$ or $b<2$, it returns $a+b$.

Otherwise, it returns the maximum of the following four expressions (all divisions are integer divisions):

$$a+b$$ $$g(a/2)+g(a/3)+g(a/8)+g(a/9)+b$$ $$g(b/2)+g(b/3)+g(b/8)+g(b/9)+a$$ $$g(b/2)+g(b/3)+g(b/8)+g(b/9)+g(a/2)+g(a/3)+g(a/8)+g(a/9)$$

Here, $g(n)$ returns $\max(g(n/2)+g(n/3)+g(n/8)+g(n/9),n)$, and it returns $0$ when $n=0$.

Of course, even an idiot can figure out that you can use memoization to compute smaller values of $f(a,b)$, so Xiaoben will not test you with such an easy problem.

He wants you to find the value of $f(a,b)$ when both $a$ and $b$ are less than $10^{16}$.

Input Format

The input contains multiple test cases.

Each test case consists of one line with two positive integers $a,b$.

Output Format

For each test case, output one line containing the value of $f(a,b)$.

5 6
1 1
1 223

11
2
224

Hint

For $40\%$ of the testdata, $a,b<10^7$.

For $70\%$ of the testdata, the time limit is $2$ seconds.

For $100\%$ of the testdata, $a,b<10^{16}$. The number of test cases does not exceed $10^4$.

Translated by ChatGPT 5