eolymp
bolt
Try our new interface for solving problems
Problems

Перестройка паутины

Перестройка паутины

Time limit 2 seconds
Memory limit 64 MiB

Старому пауку захотелось внести разнообразие в свою жизнь. Для этого он решил перестроить свою прямоугольную паутину. Изначально паутина представляет собой прямоугольник размером a×b. За одну секунду паук может сделать одну из следующих операций с паутиной x×y:

  1. Довязать к паутине полоску x×k так, что получится прямоугольник x×(y+k), для любого натурального ky, являющегося делителем числа y.

  2. Довязать к паутине полоску k×y так, что получится прямоугольник (x+k)×y, для любого натурального kx, являющегося делителем числа x.

  3. Отрезать от паутины полоску размером x×k так, что получится прямоугольник x×(y-k), для любого натурального k < y, являющегося делителем числа y.

  4. Отрезать от паутины полоску размером k×y так, что получится прямоугольник (x-k)×y, для любого натурального k < x, являющегося делителем числа x.

Вам известны начальные размеры паутины и размеры, которые хочет получить паук. Ваша задача вычислить, какое минимальное время ему для этого понадобится. Ориентация паутины не имеет значения (a×b и b×a – одинаковые паутины).

Input data

Четыре целых числа a, b, c, d (1a, b, c, d10^5).

Output data

Единственное число – минимальное время в секундах, необходимое для перестройки паутины a×b в паутину c×d.

Examples

Input example #1
5 2 2 3
Output example #1
2
Author Andrej Selivanov
Source "Five for week" 05 (2013-2014), Breadth First Search