Problem Description

Given an integer $K$ and a prime number $m$, find the smallest positive integer $N$ such that $11\cdots1$ ($N$ digits of $1$) $\equiv K \pmod m$.

In plain words: $111\cdots 1111 \bmod m = K$.

Input Format

The first line contains two integers, representing $K$ and $m$.

Output Format

Output one integer, the smallest $N$ that satisfies the condition.

9 17

3

Hint

For $30\%$ of the testdata, $m \leq 10^6$.

For $60\%$ of the testdata, $m \leq 5 \times 10^7$.

For $100\%$ of the testdata, $6 \leq m \leq 10^{11}$, $0 < K < m$, and $m$ is guaranteed to be prime.

Translated by ChatGPT 5