题目描述

有 $n$ 条香肠，每条香肠的长度相等。我们打算将这些香肠切开后分给 $k$ 名客人，且要求每名客人获得一样多的香肠，且要将所有的香肠分配完，不做保留。

请问最少需要切几刀才能完成？一刀只能切断一条香肠，每一个客人都可以接受多段香肠。

输入格式

两个整数：$n$ 与 $k$。

输出格式

单个整数：表示最少需要切几刀。

数据范围

• 对于 $40\%$的数据，$1\leq n,k\leq 50$；
• 对于 $70\%$的数据，$1\leq n,k\leq 5000$；
• 对于 $100\%$的数据，$1\leq n,k\leq 5,000,000$。
• 对于附加数据，$1\leq n,k\leq 10^{15}$。

样例数据

输入:

2 6

输出:

4

说明:

两根香肠六人分，每根香肠切成3段，共4刀

输入:

6 2

输出:

0

说明:

六根香肠两人分，不需要切

输入:

3 4

输出:

3

说明:

在每根香肠的1/4处切开，有三人每人得到3/4根香肠，最后一人得到三个1/4长的香肠。