题目描述

Perfect binary trees are one of the coolest structures that computer scientists study. They have a lot of properties that make them very nice to work with. One of the nicest properties is that they can just be described by a single integerngiving the depth of the tree. For instance, the perfect binary tree forn= 3 looks like:

In general, a perfect binary tree with depthnwill have exactly 2n+1 – 1 nodes, and can be numbered by following the pattern seen above (there are of course other ways to number the nodes of the tree, but this is the scheme we will use in this problem).

A common question that arises when dealing with trees is the query of the lowest common ancestor (commonly called LCA) of two nodes in the tree. Formally, the LCA ofxandyis the nodezof greatest depth in the tree such thatzis an ancestor ofxandy. Nodeais an ancestor of nodecifcexists in the sub-tree rooted at nodea. Notice that 1 is trivially a common ancestor of any two nodes in the tree, but is not always thelowestcommon ancestor. For instance, the common ancestors of nodes 7 and 12 are 1 and 3, and 3 is the LCA since it is the node of greatest depth. The LCA of 2 and 13 is node 1, and the LCA of 5 and 11 is node 5. The definition of LCA guarantees that the LCA of any two nodes will always be unique.

The Problem:

Given two nodes in the tree using the numbering scheme shown above, determine the LCA of the two nodes.

输入格式

Input will begin with apositive integer,T≤ 2∙10⁶,indicating the number of test cases. Thiswill be followed byTtest cases, each on a separate inputline. Each test case will contain twospace separated integers,XandY, represented in hexadecimal.XandYwill each contain at most 1000characters from the set {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}, where a-frepresent 10-15, respectively. You are todetermine the LCA ofXandY.

Note: The hexadecimal (base 16) numberdndn-1···d1d0 is converted to a decimal number (base 10) by the followingformula:d0·16⁰ +d1·16¹ + ··· +dn-1·16^n-1 +dn·16ⁿ.

输出格式

For each case, output a singleline:

Case#x:y

wherexis the case number beginning with 1, andyis the LCA in hexadecimal with no leading 0’s. Leave a blankline after the output for each testcase.

样例

7
7 c
2 d
b 5
10 11
a020fac a030ccf
12afcdb 12afcdc
100000000 fffffffff

Case #1: 3

Case #2: 1

Case #3: 5

Case #4: 8

Case #5: 501

Case #6: 255f9b

Case #7: 1