The 666-th problem - MarisaOJ: Marisa Online Judge

The 666-th problem

Time limit: 1000 ms
Memory limit: 256 MB
Reisen is studying numbers, specifically, she picks a digit $d$ $(0 \le d \le 9)$ and repeats it many times to form a new number in the form $ddd...ddd$. This type of number is called a repeated number of digit $d$. Currently, Reisen has a number $n$ and a digit $d$, and she needs to find the shortest repeated number of digit $d$ that is a multiple of $n$. Reisen is very afraid of being haunted by the demon Satan, so she tends to avoid numbers related to the number $666$, such as numbers $6$, $66$, $666$, $6666$, etc., so her digit $d$ must not be $6$. Help Reisen calculate the minimum number of digits of a repeated number of $d$ that is a multiple of $n$. ### Input - Contains two positive integers $n, d.$ ### Output - Output the result of the problem, and the result will be $0$ if no such repeated number exists. ### Constraints - $0 \le d \le 9,$ $d \neq 6.$ - $1 \le n \le 10^9.$ ### Example Input ``` 11 3 ``` Output ``` 2 ``` ### Image