{"raw_statement":[{"iden":"problem statement","content":"We have a positive integer $a$. Additionally, there is a blackboard with a number written in base $10$.  \nLet $x$ be the number on the blackboard. Takahashi can do the operations below to change this number.\n\n*   Erase $x$ and write $x$ multiplied by $a$, in base $10$.\n*   See $x$ as a string and move the rightmost digit to the beginning.  \n    This operation can only be done when $x \\geq 10$ and $x$ is not divisible by $10$.\n\nFor example, when $a = 2, x = 123$, Takahashi can do one of the following.\n\n*   Erase $x$ and write $x \\times a = 123 \\times 2 = 246$.\n*   See $x$ as a string and move the rightmost digit `3` of `123` to the beginning, changing the number from $123$ to $312$.\n\nThe number on the blackboard is initially $1$. What is the minimum number of operations needed to change the number on the blackboard to $N$? If there is no way to change the number to $N$, print $-1$."},{"iden":"constraints","content":"*   $2 \\leq a \\lt 10^6$\n*   $2 \\leq N \\lt 10^6$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$a$ $N$"},{"iden":"sample input 1","content":"3 72"},{"iden":"sample output 1","content":"4\n\nWe can change the number on the blackboard from $1$ to $72$ in four operations, as follows.\n\n*   Do the operation of the first type: $1 \\to 3$.\n*   Do the operation of the first type: $3 \\to 9$.\n*   Do the operation of the first type: $9 \\to 27$.\n*   Do the operation of the second type: $27 \\to 72$.\n\nIt is impossible to reach $72$ in three or fewer operations, so the answer is $4$."},{"iden":"sample input 2","content":"2 5"},{"iden":"sample output 2","content":"\\-1\n\nIt is impossible to change the number on the blackboard to $5$."},{"iden":"sample input 3","content":"2 611"},{"iden":"sample output 3","content":"12\n\nThere is a way to change the number on the blackboard to $611$ in $12$ operations: $1 \\to 2 \\to 4 \\to 8 \\to 16 \\to 32 \\to 64 \\to 46 \\to 92 \\to 29 \\to 58 \\to 116 \\to 611$, which is the minimum possible."},{"iden":"sample input 4","content":"2 767090"},{"iden":"sample output 4","content":"111"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}