Перебудова павутини
Старому павуку захотілось внести різноманітність у своє життя. Для цього він вирішив перебудувати свою прямокутну павутину. Спочатку павутина являє собою прямокутник розміром 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.