Nitoiu

Nitoiu found out that he sings really reaally bad so he wants a career change. While expanding his skillset, he discovered that he is very good at arithmetic operations.

His old producer Sake doesn't like the idea of losing a long time collaborator so he wants to discourage Nitoiu by proving that he is not as good at arithmetics as he thinks he is.

Sake gives Nitoiu two integers $N$, $K$ and asks him the minimum number of concatenations of $N$ with itself such that the result is divisible by $K$. If by concatenating $N$ with itself any number of times it is impossible to find a multiple of $K$ the answer is considered $-1$.

Nitoiu promises that he will cover your favorite song if you help him with this task.

Input data

The only line contains two integers $N$ and $K$ ($1 \leq N \leq 10^9$, $1 \leq K \leq 10^5$).

Output data

Output a single integer - the minimum number of concatenations needed to obtain a multiple of $K$ or -1 if this is impossible.

Constraints and clarifications

• For $20$ points it is guaranteed that $N < 10$, $K \leq 18$ and the lowest multiple is less than $10^{18}$
• For another $20$ points it is guaranteed that $N < 10$, $K \leq 1 \ 000$ and the result is less than $10^4$.
• For another $20$ points it is guaranteed that $N < 10$, $K \leq 10^5$ and the result is less than $10^7$.
• For another $20$ points it is guaranteed that $N \leq 1 \ 000$, $K \leq 10^5$ and the result is less than $10^7$.
• The last $20$ points are given for tests where $N \leq 10^9$ and $K \leq 10^5$.

Example

stdin

2 6

stdout

2

Explanation

The minimum number of concatenations needed is $2$ because $222$ is divisible by $6$ and $22$ is not divisible by $6$.