The old spider wanted to add some variety to its life. To do so, it decided to reconstruct its rectangular web. Initially, the web has dimensions a \times b. In one second, the spider can perform one of the following operations on a web of size x \times y:
Attach a strip of size x \times k to the web, resulting in a rectangle of size x \times (y + k), where is any natural number divisor of and k \leq y.
Attach a strip of size k \times y to the web, resulting in a rectangle of size (x + k) \times y, where is any natural number divisor of and k \leq x.
Cut off a strip of size x \times k from the web, resulting in a rectangle of size x \times (y - k), where is any natural number divisor of and k < y.
Cut off a strip of size k \times y from the web, resulting in a rectangle of size (x - k) \times y, where is any natural number divisor of and k < x.
You are given the initial dimensions of the web and the target dimensions that the spider wants to achieve. Your task is to determine the minimum time required to achieve this transformation. The orientation of the web does not matter (a \times b and b \times a are considered equivalent).
Four integers , , , (1 \leq a, b, c, d \leq 10^5).
Print a single integer — the minimum number of seconds needed to transform the web from a \times b to c \times d.
Example 1