A Meaningless Problem

 Time limit: 1 second

 Memory limit: 64 megabytes

Once upon a time, Glory was wandering in a mysterious forest. Suddenly, he was attracted by a fascinating tree, which is surprisingly a perfect binary tree. There was an infinity numbers of leaves on this tree. Glory was so curious that he wanted to know its structure in a meaningless way. To fulfill his wish, let’s assume that its numbering is shown as the figure below. That is to say, you need to help him answer the least common ancestor between two given nodes. Figure 1: *

Least common ancestor Figure 2: *

Binary trees

Input

The input contains several test cases ending with EOF.

For each test case, only one line contains two integer a and b indicating the two nodes.

We guarantee that the length of a + b in the decimal code is up to 2 000 in one test, and the total length of all a s and b s is up to 20 000.

Output

For each test case, output a line containing an integer indicating the least common ancestor between two given nodes.

12 7

3