12440번 - 계산식 복원 (Large)

아홉글 출판사에서는 2012년 새 학기를 맞이하여 초등학생을 위한 수학 문제집을 제작하였다. 이 문제집은 초등학교 저학년을 위한 계산 연습 문제집으로 많은 문제가 들어 있어 학구열이 높은 부모님 사이에서 인기가 높다. 이를 시기한 경쟁 출판사에서 새 문제집이 출판되기 직전 몰래 문제집 원고에 손을 대 문제에 주어진 숫자들을 마구잡이로 지워 놓았다. 이 문제집이 무사히 출판될 수 있도록 지워진 숫자들을 찾아주자.

• 수식은 "숫자 연산자 숫자 = 숫자" 형태로 표현된다.
• 사용되는 연산자는 덧셈(+) 또는 뺄셈(-)이다.
• 모든 숫자는 음이 아닌 정수이며, 0으로 시작하는 양의 정수는 없다.
• 숫자의 지워진 각 자리는 ?로 표시된다.
• 위 수식에서 숫자와 연산자 사이, 숫자와 = 사이에는 공백 문자 하나만이 존재한다.
• 수식의 가장 앞과 가장 뒤에는 공백 문자들이 없다.

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 아래로 T 줄의 입력이 주어지며 각 줄은 하나의 테스트 케이스에 대한 입력이다. 각 테스트 케이스는 아래와 같이 하나의 수식이 주어진다.

1?3 + 24? = 424

제한

• 1 ≤ T ≤ 100.
• 1 ≤ 수식의 길이 ≤ 250.

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 복원된 수식이다. 복원된 수식이 여러 개가 가능할 경우, 각각의 수식을 문자열로 보았을 때 사전 순으로 가장 작은 수식을 출력한다. 예를 들어서 아래의 세 번째 예제에서, "10 - 7 = 3" 은 "11 - 8 = 3"이나 "12 - 9 = 3" 보다 작으므로 그것을 답으로 출력해야 한다.