B. Nitoiu
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

Output

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

Scoring
  • for 20 points it is guaranteed that $$$N \lt 10$$$, $$$K \leq 18$$$ and the lowest multiple is less than $$$10^{18}$$$
  • for another 20 points it is guaranteed that $$$N \lt 10$$$, $$$K \leq 1000$$$ and the result is less than $$$10^4$$$.
  • for another 20 points it is guaranteed that $$$N \lt 10$$$, $$$K \leq 10^5$$$ and the result is less than $$$10^7$$$.
  • for another 20 points it is guaranteed that $$$N \leq 1000$$$, $$$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
Input
2 6
Output
2
Note

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