Problem E: Little Six is Puzzled

Problem E: Little Six is Puzzled

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 39  Solved: 11
[Submit][Status][Web Board]

Description

In front of Little Six, there are two tubes which are opening in both ends. There are several balls placed in each tubes, and each ball has a digit from \(1\) to \(9\) printed on it.

Each time Little Six can choose a tube, and choose one of the two ends of that tube, and then take out the most outside ball from that end (unless there are no balls left in the tube). Therefore, Little Six have many choices of sequences to take out all of the balls.

After taking out all of the balls in some sequence, Little Six can form up a decimal integer. Specifically, if the digits on the balls in the order of being taken out is \(a_1, a_2, ..., a_n\), then the integer formed up is \(\overline{a_1 a_2 ... a_n}\).

Little Six hopes to get the biggest integer. Can you help him?

Input

The first line contains an integer \(T(T\leq 14)\), representing the number of test cases.

Then \(T\) lines follows. Each line contains two strings which only consist of digits from \(1\) to \(9\), representing the digits on the balls in the two tubes. Each tube has at least one ball and at most \(40\) balls.

Output

For each test case, output one line `Case #x: A` where \(x\) is the serial number of the test case and \(A\) is the maximum integer.

Sample Input

2
123456 123456
9876346789 9854894589

Sample Output

Case #1: 665544332211
Case #2: 99998888776655498443

HINT

[Submit][Status]