Перестройка паутины
Старому пауку захотелось внести разнообразие в свою жизнь. Для этого он решил перестроить свою прямоугольную паутину. Изначально паутина представляет собой прямоугольник размером a×b. За одну секунду паук может сделать одну из следующих операций с паутиной x×y:
Довязать к паутине полоску x×k так, что получится прямоугольник x×(y+k), для любого натурального k ≤ y, являющегося делителем числа y.
Довязать к паутине полоску k×y так, что получится прямоугольник (x+k)×y, для любого натурального k ≤ x, являющегося делителем числа x.
Отрезать от паутины полоску размером x×k так, что получится прямоугольник x×(y-k), для любого натурального k < y, являющегося делителем числа y.
Отрезать от паутины полоску размером k×y так, что получится прямоугольник (x-k)×y, для любого натурального k < x, являющегося делителем числа x.
Вам известны начальные размеры паутины и размеры, которые хочет получить паук. Ваша задача вычислить, какое минимальное время ему для этого понадобится. Ориентация паутины не имеет значения (a×b и b×a – одинаковые паутины).
Входные данные
Четыре целых числа a, b, c, d (1 ≤ a, b, c, d ≤ 10^5).
Выходные данные
Единственное число – минимальное время в секундах, необходимое для перестройки паутины a×b в паутину c×d.