누락된 숫자
시간 제한1초메모리 제한128 MB
A와 B 중 한 숫자에 x로 가려진 한 자리 숫자를 0부터 9까지 넣어 A가 B로 나누어떨어지게 하는 가장 작은 숫자를 구합니다.
문제
헥토르(Hektor)와 빅토르(Wiktor)는 자신들만의 암호화 시스템을 개발하고 있습니다. 진행은 더디지만, 지금까지 숫자로 이루어진 수열을 어떻게 암호화할지는 정했습니다.
암호화할 수열은 한 자리 숫자 하나하나로 분해되어 각각 따로 부호화됩니다. 한 자리 숫자 d의 암호문은 두 개의 양의 정수 A와 B로 이루어집니다. 이 두 수 중 정확히 하나에서, 정확히 한 자리의 숫자가 문자 'x'로 바뀌어 있습니다. A, B와 'x'의 위치는, 암호화된 숫자 d가 'x' 자리에 넣었을 때 A를 B로 나누어떨어지게 만드는 가장 작은 숫자가 되도록 정해집니다.
헥토르와 빅토르는 암호화 프로그램은 이미 만들었고, 여러분에게 복호화 프로그램을 만들어 달라고 부탁했습니다.
A와 B는 앞자리에 0을 가질 수 없으므로, 'x'가 어떤 수의 맨 앞자리에 있다면 그 자리에 넣는 숫자는 1부터 9까지여야 합니다(0은 올 수 없습니다).
입력
첫 번째 줄에는 테스트 세트의 개수를 나타내는 자연수 Z ()가 주어집니다. 이어서 각 테스트 세트가 차례로 주어집니다.
각 테스트 세트의 첫 번째 줄에는 암호화된 수열의 자릿수를 나타내는 정수 N ()이 주어집니다. 이어지는 N개의 줄에는 부호화된 수열의 한 자리 숫자에 대한 암호문이 각각 주어지며, 공백 하나로 구분된 두 정수 A와 B ()로 이루어집니다. 이 두 수 중 정확히 하나에서 정확히 한 자리의 숫자가 문자 'x'로 바뀌어 있습니다.
A와 B는 모두 앞자리에 0을 가지지 않습니다(0으로 시작하지 않습니다).
출력
각 테스트 세트마다, 입력으로 주어진 암호문에 해당하는 숫자 수열을 한 줄에 하나씩 출력합니다. 출력하는 답의 순서는 입력에 주어진 테스트 세트의 순서와 같아야 합니다.
설명
몇 가지 한 자리 숫자 암호문을 살펴봅시다.
2x 23은 3으로 복호화됩니다. 23이 23으로 나누어떨어지고, 더 작은 숫자를 x 자리에 넣으면 나누어떨어지지 않기 때문입니다.29x 9는 7로 복호화됩니다. 297이 9로 나누어떨어지기 때문입니다.1331 x1은 1로 복호화됩니다. 1331이 11로 나누어떨어지기 때문입니다.45825 1x는 3으로 복호화됩니다. 45825가 13으로 나누어떨어지기 때문입니다.