Professor Conrad loves to work with expressions and we all know that there are many well known techniques to evaluate expressions. After teaching his class about evaluating expression he gives his class a bit tricky assignment. As usual being the most brilliant programmer of the class, your classmates have grasped you to do the assignment for them. The assignment is stated below: You are given an expression consisting only brackets, blank spaces and +/− operators and also some digits. You have to place the given digits in the blank spaces in such a way so that the value of the expression is maximum. Input First line of the input file contains an integer N (N ≤ 505) which denotes how many sets of inputs will be there. The description of each set is given below. First line of each set contains a correct expression and the second line contains a sequence of digits. You can put any of this one of these digits in the blank spaces of the expression. In the input the blank spaces are denoted with ‘#’ characters. You can assume that (a) The number of ‘#’ signs in the expression and the number of given digits will be equal (b) There will be maximum eight consecutive ‘#’ signs in the given expression (c) The length of the expression will be less than 200 Output For each set of input produce three lines of output. First line contains the serial of output, the second line contains the expression which produces maximum value and the third line contains this maximum value. If more than one expression produces maximum value then output the lexicographically smallest one. You can assume that (a) the maximum value of the expression will fit in a 32-bit signed integer (b) Numbers in the expression can have leading zeroes. Sample Input 3 ##-(##+###) 3333333 #+# 31 #-# 31
2/2 Sample Output Case 1: 33-(33+333) -333 Case 2: 1+3 4 Case 3: 3-1 2