Profesor HwKwan sa venuje umelej inteligencii a vo svojom laboratóriu prevádza všakovaké experimenty. Jeho posledným úspechom je robot Kubikus. Dokáže sa pohybovať po vyznačenej štvorcovej sieti a pri tom plniť jednoduché úlohy.
Jednou z prvých úloh, ktoré pripravil profesor pre robota, bolo očíslovanie štvorcovej siete. Kubikusa postavil doprostred jedného z políčok štvorcovej siete a zadal mu nasledujúcu postupnosť príkazov:
- 1. nastav počítadlo N=1
- 2. očísluj políčko, na ktorom práve stojíš, číslom N
- 3. zväčši počítadlo N o 1
- 4. ak je políčko po tvojej pravej strane neočíslované, otoč sa o 90 stupňov doprava
- 5. postúp o krok dopredu (na políčko pred tebou)
- 6. ak si ešte stále v štvorcovej sieti, choď na krok 2.
Kubikus sa nedal zahanbiť a po chvíli boli políčka očíslované. Teraz mu už mohol profesor HwKwan zadávať príkazy typu „presuň sa na políčko číslo 5“, „presuň sa na políčko číslo 22“ a pod. Kubikus sa môže po štvorcovej sieti pohybovať len horizontálne a vertikálne. Ak sa má napríklad z aktuálneho políčka na ktorom stojí presunúť na políčko, ktoré leží o 2 rady naľavo a 3 vpredu, potrebuje na to 5 krokov. Profesor HwKwan by chcel skontrolovať, či dokáže Kubikus nájsť medzi dvomi zadanými políčkami štvorcovej siete najkratšiu cestu.
Úloha
Napíšte program, ktorý pri vyššie definovanom očíslovaní štvorcovej siete určí, koľko krokov musí prejsť Kubikus po najkratšej ceste medzi dvomi zadanými políčkami.
Vstup
Vstup pozostáva z niekoľkých riadkov (nie viac ako 1000). Každý riadok obsahuje dvojicu čísel M a N (1 < M,N < 999999999) oddelených jednou medzerou, udávajúcich počiatočné a koncové políčko cesty, ktorú má Kubikus prejsť. Vstup je ukončený riadkom obsahujúcim 0 0.
Výstup
Pre každý riadok treba na výstup zapísať jediný riadok obsahujúci číslo udávajúce koľko krokov musí prejsť Kubikus po najkratšej ceste medzi políčkami M a N.
Príklad
Vstup:
1 2
3 4
1 123
1234 5678
1 99999999
0 0
Výstup:
1
1
10
44
9998
|