410273: GYM103999 B 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.

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

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

• 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 1000$$$ 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 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$$$.

2 6

2

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