Codeforces Round 547 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

implementation

math

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Game 23

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp plays "Game 23". Initially he has a number $$$n$$$ and his goal is to transform it to $$$m$$$. In one move, he can multiply $$$n$$$ by $$$2$$$ or multiply $$$n$$$ by $$$3$$$. He can perform any number of moves.

Print the number of moves needed to transform $$$n$$$ to $$$m$$$. Print -1 if it is impossible to do so.

It is easy to prove that any way to transform $$$n$$$ to $$$m$$$ contains the same number of moves (i.e. number of moves doesn't depend on the way of transformation).

Input

The only line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m \le 5\cdot10^8$$$).

Output

Print the number of moves to transform $$$n$$$ to $$$m$$$, or -1 if there is no solution.

Examples

Input

120 51840

Output

7

Input

42 42

Output

0

Input

48 72

Output

-1

Note

In the first example, the possible sequence of moves is: $$$120 \rightarrow 240 \rightarrow 720 \rightarrow 1440 \rightarrow 4320 \rightarrow 12960 \rightarrow 25920 \rightarrow 51840.$$$ The are $$$7$$$ steps in total.

In the second example, no moves are needed. Thus, the answer is $$$0$$$.

In the third example, it is impossible to transform $$$48$$$ to $$$72$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 18:10:09 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|