Description

给定两个正整数 a 和 b。每次操作可以把 a 乘以 b 的任意一个质因子。问最少操作多少次，才能使 a 变成 b 的倍数。如果 a 已经是 b 的倍数，输出 0。

Input Format

一行两个正整数 a 和 b。

Output Format

一行一个整数，表示最少操作次数。

12 72

1

Hint

分解 b 的质因子，比较 a 中对应质因子的指数缺口，所有缺口之和就是答案。