체크섬

검사 합(체크섬)은 데이터를 전송하거나 입력할 때 생기는 오류를 찾는 데 쓰인다. 이를 위해 여러 알고리즘이 고안되었다. 이 문제는 그중 가장 단순한 방법을 다룬다.

수열 $(A_1, A_2, \ldots)$의 체크섬은 다음과 같이 정의된다.

$(A_1 \cdot K_1 + A_2 \cdot K_2 + \ldots + A_N \cdot K_N + A_{N+1} \cdot K_1 + \ldots) \bmod 10$

여기서 $K_1, K_2, \ldots, K_N$은 정해진 상수이다. 수열 $K$는 주기적으로 취급한다. $A$의 길이가 $K$보다 길면 $K$의 원소를 처음부터 다시 사용한다. $A$가 더 짧으면 $K$의 일부 원소는 사용되지 않는다.

주쿠는 이 체크섬을 사용하는 시스템을 찾아냈다. 하지만 이 시스템의 수열 $K$ 길이 $N$과 원소 $K_i$의 값은 알지 못한다. 알고 있는 것은 $N \le 1\,000$이고 $1 \le K_i \le 9$라는 사실뿐이다. 주쿠는 시스템에 질의를 보낼 수 있다. 각 질의는 숫자열이며, 시스템은 그 숫자열의 체크섬을 답으로 돌려준다. 주쿠의 키보드는 0 키가 약간 고장 나 있어 0을 입력하기 어렵다. 그래서 질의에 숫자 0을 쓰지 않으려 한다.

수열 $K$의 길이와 원소 값을 구하는 프로그램을 작성하라. $K$는 주기적이므로 가능한 답은 무수히 많다. 그중 가장 짧은 답을 출력하라.