계산식 복원 (Small)

덧셈식이나 뺄셈식의 ?마다 숫자를 채워 등식을 성립시키고 전체 문자열이 사전 순으로 가장 작게 만듭니다.

쉬움3완전 탐색문자열수학아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

한 출판사가 2012년 새 학기에 맞춰 초등학교 저학년용 계산 연습 문제집을 만들었다. 문제 수가 많아 학구열 높은 부모 사이에서 인기가 높았다. 이를 시기한 경쟁 출판사가 출판 직전에 원고에 손을 대 문제에 있던 숫자를 마구잡이로 지워 놓았다. 문제집이 무사히 나올 수 있도록 지워진 숫자를 찾아내자.

  • 수식은 숫자 연산자 숫자 = 숫자 형태다.
  • 연산자는 덧셈 + 또는 뺄셈 -이다.
  • 모든 숫자는 음이 아닌 정수이고, 0으로 시작하는 양의 정수는 없다. 즉 두 자리 이상인 숫자의 첫 자리는 0이 아니다.
  • 숫자에서 지워진 자리는 ?로 표시한다.
  • 숫자와 연산자 사이, 숫자와 = 사이에는 공백 문자가 하나씩만 있고, 수식의 맨 앞과 맨 뒤에는 공백이 없다.
  • 숫자가 지워지기 전의 수식이 실제로 있었으므로 각 수식마다 복원 결과가 적어도 하나 있다.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다. 이어지는 TT개의 줄에 각각 수식이 하나씩 주어지며, 숫자의 일부 자리가 ?로 지워져 있다.

제한

  • 1T1001 \le T \le 100
  • 수식의 길이는 11 이상 2020 이하다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 복원한 수식이다.

복원 결과가 여러 개면 수식 전체를 하나의 문자열로 보았을 때 사전순으로 가장 작은 것을 출력한다. 예를 들어 1? - ? = 310 - 7 = 3, 11 - 8 = 3, 12 - 9 = 3으로 복원할 수 있고, 이 중 사전순으로 가장 작은 10 - 7 = 3을 출력한다.