Equation restoration (Small)

Fill each ? in an addition or subtraction equation with a digit so the equation holds and the whole string is lexicographically smallest.

Easy3Brute forceStringMathNo attempts yetTime limit5sMemory limit512 MB

Problem

A publisher put together an arithmetic drill book for the lower grades of elementary school for the 2012 school year. The book holds a lot of problems, so it was popular among parents who push their children hard. A rival publisher got jealous, reached the manuscript right before printing, and erased digits from the problems at random. Find the erased digits so the book can still be printed.

  • An equation has the form number operator number = number.
  • The operator is addition + or subtraction -.
  • Every number is a non-negative integer, and no positive integer starts with 0. A number of two or more digits therefore never begins with 0.
  • Each erased digit is written as ?.
  • Exactly one space separates a number from the operator and from =, and the equation has no space at its start or end.
  • The equation existed before its digits were erased, so every equation has at least one restoration.

Input

The first line contains the number of test cases TT. Each of the next TT lines contains one equation in which some digits have been erased to ?.

Constraints

  • 1T1001 \le T \le 100
  • The length of an equation is at least 11 and at most 2020.

Output

For each test case, print one line in the form Case #x: y, where xx is the test case number starting from 1 and yy is the restored equation.

When several restorations are possible, read the whole equation as one string and print the smallest one in lexicographic order. For example, 1? - ? = 3 can be restored to 10 - 7 = 3, 11 - 8 = 3 or 12 - 9 = 3, and the smallest of the three is 10 - 7 = 3.