解题思路

给定两种操作：把当前数乘以 x 或乘以 y。若能从 a 变到 b，设比例 r = b / a（必须满足 b % a == 0），那么一切操作的乘积等价于把 r 分解成

此时最少操作次数就是使用的总步数 i + j。因此问题转化为：判断 r 是否能表示为 x^i * y^j，并在可行时最小化 i + j。

题目内容

小红可以对一个数进行如下两种操作：将这个数乘以 $x$ 或将这个数乘以 $y$ 。操作的次数是没有限制的。

小红想知道，自己最少经过多少次操作以后，可以把 $a$ 变成 $b$ ?

输入描述

四个正整数 $x,y,a,b$，用空格隔开。

$2 ≤ x,y ≤ 100$

$1 ≤ a,b≤ 10^9$

输出描述

如果小红无论如何都无法把 $a$ 变成 $b$ ，则输出 $-1$ 。否则输出小红操作的最少次数。可以证明，如果存在某种操作，那么最少次数定是固定的。

样例1

输入

2 3 5 20

输出

2

说明

$x=2,y=3$，进行两次乘 $2$ 操作，可以把 $5$ 变成 $20$ 。