Как-то раз, сидя на не самом интересном уроке по математике, Вася собирал оригами из прямоугольного листа бумаги a мм × b мм (a > b). Как правило, первым шагом при сборке оригами является получение квадратной заготовки из прямоугольного листа бумаги путём сгибания вдоль биссектрисы прямого угла и отрезания лишней части.
Собрав бумажный кораблик из квадратной заготовки, Вася обратил внимание на оставшуюся полоску бумаги (a - b) мм × b мм. Ему пришла в голову мысль использовать аналогичным образом эту полоску для создания оригами, а затем оставшуюся (если такая образуется) и так далее. В тот момент, когда в качестве остатка у него окажется квадратный фрагмент бумаги, он соберёт из него последний кораблик и остановится.
Можете ли вы определить, сколько всего корабликов соберёт Вася за урок?
Выходные данные
Выведите единственное целое число — количество корабликов, которые соберёт Вася.
Примечание
Иллюстрации к первому и второму тесту из условия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
|
2
|
|
2
|
10 7
|
6
|
|
3
|
1000000000000 1
|
1000000000000
|