Sparing w Programowaniu Zespołowym UAM & PP, 6.11.2004

Opis

W pewnym mieście w Bajtocji układ dróg do złudzenia przypomina zeszytową kartkę w kratkę, gdzie odległość między kolejnymi równoległymi do siebie ulicami wynosi dokładnie 1 kilometr. Jak łatwo zauważyc taka sama odległość dzieli wszystkie najbliższe skrzyżowania. Naszym zadaniem jako taksówkarza będzie startując na pewnym wybranym skrzyżowaniu odwiedzenie kolejno podanych skrzyżowań. Niestety ograniczono w tym mieście możliwość skręcania. Na skrzyżowaniu możemy jeedynie pojechać prosto lub skręcić w prawo.

Specyfikacja wejścia

W pierwszym wierszu znajduje się liczba D oznaczająca liczbę zestawów testowych. Dla każdego zestawu w pierwszym wierszu pojawią się dwie liczby naturalne X, Y (-10^9 ≤ X, Y ≤ 10^9) oznaczające współrzędne skrzyżowania (przedstawionych w układzie współrzędnych euklidesowych), w którym znajduje się Twoja taksówka. Z tego skrzyżowania możemy ruszyć się w dowolnym kierunku. W kolejnym wierszu znajduje się pojedyncza liczba N (1 ≤ N ≤ 10^6) oznaczająca liczba skrzyżwoań, które musimy odwiedzić w podanej kolejności. W kolejnych N liniach znajdują się współrzędne X_i, Y_i (-10^9 ≤ X_i, Y_i ≤ 10^9) kolejnych skrzyżowań.

Specyfikacja wyjścia

Dla każdego zestawu danych należy wypisać w osobnej linii jedną liczbę naturalną oznaczająca minimalną liczbę kilometrów, które musimy pokonać, aby odwiedzić wszystkie skrzyżowania w podanej kolejności.

Przykład

2
0 0
2
1 1
2 0
-1 -1 
2
-1 0
-2 0

4
6