Description

艺术学院的同学做毕业设计，要用各种铁片正方形，现给出边长为整数的矩形铁片，用剪刀将其裁切成大大小小的正方形，为节约材料，要求剪完之后无边角剩料。问最少可以裁出多少正方形。

Input

成对输入若干个正整数 n，m(1<n,m<2^31)作为铁片的长宽。

Output

输出裁好的最少正方形数。

Sample

Input

1 1
2 1
9 10

Output

1
2
10

Source: qn