교대

두 양의 정수 $A,B$에 대해 $A \star B$를 다음과 같이 정의한다.

먼저 $A$와 $B$의 자릿수가 같아지도록, 자릿수가 더 짧은 수의 앞에 $0$을 붙인다. 그 후 $A$의 첫 번째 자릿수, $B$의 첫 번째 자릿수, $A$의 두 번째 자릿수, $B$의 두 번째 자릿수, $\ldots$ 순서로 자릿수를 번갈아 적는다.

이렇게 얻은 문자열을 하나의 십진수로 읽은 값이 $A \star B$이다. 앞에 오는 $0$은 무시한다.

예를 들어 $A=12$, $B=3456$이면 $A$를 $0012$로 생각하므로

이다.

양의 정수 $B$와 소수 $P$가 주어진다. $A \star B$가 $P$로 나누어떨어지도록 하는 최소의 양의 정수 $A$를 구하여라. 조건을 만족하는 $A$가 존재하지 않는다면 $-1$을 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$B\ P$

$B$는 앞에 불필요한 $0$이 없는 십진수 표현으로 주어진다.

첫째 줄에 $A \star B$가 $P$로 나누어떨어지도록 하는 최소의 양의 정수 $A$를 출력한다.

조건을 만족하는 $A$가 존재하지 않는다면 $-1$을 출력한다.

• $1 \leq B < 10^{10000}$.
• $2 \leq P < 100000$.
• $P$는 소수이다.