Viva la Diferencia

Time limit1sMemory limit128 MB

Summary

Given four positive integers, repeatedly replace them with the absolute differences of cyclic neighbours until all four are equal, and count the steps.

Level: Medium4 of 10
Topics: Simulation, Math, Number theory
Solved: No attempts yet

Problem

Given four positive integers $a, b, c, d$ , form four new numbers by taking the absolute differences of neighbours around a cycle:

$(\,|a-b|,\ |b-c|,\ |c-d|,\ |d-a|\,)$

Apply the same operation to the resulting four numbers, and keep repeating until all four numbers are equal.

For example, starting from $1, 3, 5, 9$ :

1  3  5  9
2  2  4  8   (step 1)
0  2  4  6   (step 2)
2  2  2  6   (step 3)
0  0  4  4   (step 4)
0  4  0  4   (step 5)
4  4  4  4   (step 6)

Here the sequence reaches four equal numbers after 6 steps. Given $a, b, c, d$ , determine how many steps it takes to converge. If the four numbers are already equal, the answer is $0$ .

Input

The input contains several test cases. Each test case is a single line with the four integers $a, b, c, d$ ( $1 \le a, b, c, d \le 2 \times 10^9$ ). The last line contains four zeros and is not processed.

Output

For each test case, print the number of steps until the four numbers become equal.

Hint

If all four integers are less than $2^n$ , the sequence converges within $3n$ steps.

Examples1

Example 1
Input
```
1 3 5 9
4 3 2 1
1 1 1 1
0 0 0 0
```
Expected output
```
6
4
0
```