{"problem":{"name":"Multiply and Rotate","description":{"content":"We have a positive integer $a$. Additionally, there is a blackboard with a number written in base $10$.   Let $x$ be the number on the blackboard. Takahashi can do the operations below to change this ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc235_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $2 \\leq a \\lt 10^6$\n*   $2 \\leq N \\lt 10^6$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$a$ $N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc235_d","tags":[],"sample_group":[["3 72","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$."],["2 5","\\-1\n\nIt is impossible to change the number on the blackboard to $5$."],["2 611","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."],["2 767090","111"]],"created_at":"2026-03-03 11:01:14"}}