题目描述

小爱手中有一张矩形纸张，他想把这张纸分成若干正方形纸片，具体分法如下：

• 第$1$步：小爱会先确定纸张的长宽，假设短边长度为$n$，长边长度为$m$。
• 第$2$步：小爱会将短边沿直角平分线对折后剪去，从而得到一个$n \times n$的方形纸片。
• 第$3$步：若还有剩余，小爱会将剩余的长宽为$n*(m-n)$的纸张作为现有纸张，代入第一步后重复之前过程，直至没有之后纸张剩余为止。

请问按如上操作，小爱最终会得到几张方形纸片？

例如：一开始，小爱有一张 $10 \times 6$ 的纸张，按他的分割方法，最终他可以获得 $4$ 张方形纸片，具体过程如下图所示：

输入格式

输入共两个正整数，表示初始矩形纸张的长宽 $m,n$

输出格式

输出题目所求能获得的矩形个数

10 6

4

数据范围

• 对于 $30 \%$ 的数据，$1 \leq n ,m \leq 100$
• 对于 $60 \%$ 的数据，$1 \leq n ,m \leq 10^7$
• 对于 $100 \%$ 的数据，$1 \leq n ,m \leq 10^{13}$