Reconstruction of the Web

The old spider wanted to introduce some variety into its life. To achieve this, it decided to reconstruct its rectangular web. Initially, the web is a rectangle with dimensions a×b. In one second, the spider can perform one of the following operations on the web x×y:

1. Attach a strip of size x×k to the web, resulting in a rectangle x×(y+k), where k is any natural number that is a divisor of y and k ≤ y.

2. Attach a strip of size k×y to the web, resulting in a rectangle (x+k)×y, where k is any natural number that is a divisor of x and k ≤ x.

3. Cut off a strip of size x×k from the web, resulting in a rectangle x×(y-k), where k is any natural number that is a divisor of y and k < y.

4. Cut off a strip of size k×y from the web, resulting in a rectangle (x-k)×y, where k is any natural number that is a divisor of x and k < x.

You are given the initial dimensions of the web and the target dimensions the spider wants to achieve. Your task is to determine the minimum time required to accomplish this transformation. The orientation of the web is irrelevant (a×b and b×a are considered equivalent).

Input

Four integers a, b, c, d (1 ≤ a, b, c, d ≤ 10^5).

Output

Output a single integer representing the minimum time in seconds needed to transform the web from a×b to c×d.

Examples