ISBN 변환

ISBN(International Standard Book Number, 국제 표준 도서 번호)은 출판된 책의 판이나 버전마다 부여되는 고유 식별자이다. 예를 들어 같은 책이라도 양장본과 문고본은 서로 다른 ISBN을 받는다. 2007년 이전에 부여된 ISBN은 10자리(ISBN-10 표준)이고, 2007년 1월 1일 이후에 부여된 ISBN은 13자리(ISBN-13 표준)이다.

2007년 이전에 나와 지금도 발행되는 책 중에는 원래의 ISBN-10과 이에 대응하는 ISBN-13을 함께 받은 책이 있다. 최근 책 중에도 하위 호환성을 위해 ISBN-10과 ISBN-13이 함께 부여되는 경우가 있다. 이 문제는 이처럼 두 가지 번호가 함께 부여되는 점을 바탕으로, 올바른 ISBN-10을 대응하는 ISBN-13으로 변환하는 문제이다.

ISBN의 마지막 자리는 간단한 오류 검출에 쓰이는 검사 숫자(checksum digit)이다. ISBN-10과 ISBN-13은 검사 숫자를 계산하고 검증하는 규칙이 다르다.

1. ISBN-10: 왼쪽부터 10개의 숫자를 $d_1, d_2, \ldots, d_{10}$이라 하자($d_{10}$이 검사 숫자이다). $S = 10 \cdot d_1 + 9 \cdot d_2 + 8 \cdot d_3 + \ldots + 2 \cdot d_9 + 1 \cdot d_{10}$ (계수는 10부터 1까지 줄어든다.) 이때 $S$는 11의 배수, 즉 $S \equiv 0 \pmod{11}$이어야 한다.
2. ISBN-13: 왼쪽부터 13개의 숫자를 $d_1, d_2, \ldots, d_{13}$이라 하자($d_{13}$이 검사 숫자이다). $S = 1 \cdot d_1 + 3 \cdot d_2 + 1 \cdot d_3 + 3 \cdot d_4 + \ldots + 3 \cdot d_{12} + 1 \cdot d_{13}$ (홀수 번째 숫자에는 1을, 짝수 번째 숫자에는 3을 곱한다.) 이때 $S$는 10의 배수, 즉 $S \equiv 0 \pmod{10}$이어야 한다.

두 규칙 모두 나머지 숫자가 정해지면 검사 숫자가 하나로 정해진다.

X의 경우: ISBN-13에는 적용되지 않고 ISBN-10에만 적용되는 작지만 중요한 세부 사항이 있다. 나눗셈 기준이 11이므로 검사 숫자는 $\{0, 1, 2, \ldots, 9, 10\}$ 중 하나의 값을 가진다. 값이 10이면 한 글자로 쓰기 위해 X로 적는다. 예를 들어 $039428013\textrm{X}$는 올바른 ISBN-10이다.

하이픈: 엄밀히 말하면 ISBN-10은 네 부분으로 이루어지며, 그중 하나가 검사 숫자이다. (처음 세 부분을 정하는 규칙은 복잡하므로 이 문제에서는 다루지 않는다.) 인접한 두 부분 사이에는 하이픈을 넣을 수도 있고 넣지 않을 수도 있다. 따라서 ISBN-10에는 하이픈이 최대 세 개까지 들어갈 수 있다. 다만 하이픈으로 시작하거나 끝날 수 없고, 하이픈이 연속으로 올 수도 없다. 하이픈이 세 개라면 반드시 검사 숫자와 그 앞 숫자 사이에 하이픈이 있어야 한다. 하이픈이 세 개보다 적다면 검사 숫자와 그 앞 숫자 사이의 하이픈은 있어도 되고 없어도 된다. 이 문제에서 다음은 올바른 ISBN-10이다.

$039428013\textrm{-X}$

$0\textrm{-}39\textrm{-}428013\textrm{X}$

$3\textrm{-}540\textrm{-}42580\textrm{-}2$

$3540425802$

다음은 잘못된 ISBN-10이다. 처음 두 개는 하이픈 위치가 잘못되었고, 마지막은 위의 검사 규칙을 통과하지 못한다.

$3\textrm{-}540\textrm{-}4258\textrm{-}02$

$3\textrm{-}540\textrm{-}425802\textrm{-}$

$0\textrm{-}14\textrm{-}028333\textrm{-}3$

ISBN-10을 ISBN-13으로 바꾸려면 (i) 앞에 $978$ 세 자리를 붙이고, (ii) 기존 검사 숫자를 지운 뒤, (iii) ISBN-13 규칙으로 정한 새 검사 숫자를 끝에 붙인다.[1] 단순하게 하기 위해 기존 하이픈의 위치는 그대로 유지하고, 앞에 붙인 978 뒤에는 하이픈을 넣는다.

1 ISBN-13은 978이 아닌 다른 세 자리로 시작할 수도 있다. 하지만 ISBN-10 앞에 붙여 대응하는 ISBN-13을 만들 수 있는 것은 978뿐이다.

첫째 줄에 정수 $T$ $(1 \leq T \leq 25)$가 주어진다. $T$는 처리할 ISBN-10의 개수이며, 잘못된 번호일 수도 있다. 이어서 $T$개의 줄이 주어진다. 각 줄에는 길이가 10 이상 13 이하인 빈 문자열이 아닌 문자열이 하나씩 주어진다. 각 문자는 10진수 숫자('0'부터 '9'), 하이픈('-'), 또는 대문자 X 중 하나이다.

각 테스트 케이스에 대해, 주어진 ISBN-10이 위의 규칙에 따라 올바르지 않다면 "invalid"를 한 줄에 출력한다. 올바르다면 대응하는 ISBN-13을 한 줄에 출력한다.