AlgoLiga 2018

W Bajtogrodzie trwają przygotowania na sylwestra.  Prezydent miasta zażyczył sobie, aby w tym roku dookoła barierek zabezpieczających obszar przeznaczony do zabawy ustawiono mnóstwo kolorowych kwiatów. Jako współorganizator imprezy Twoim zadaniem jest policzenie długości obwodu po zewnętrznej i wewnętrznej stronie zabezpieczeń, aby było wiadomo ile kwiatów należy przywieźć.

Plac przeznaczony do zabawy jest wielokątem reprezentowanym przez N punktów dodatnich. Zabezpieczenia są kwadratami o boku długości 1 i ustawiane są zawsze na liniach łączących kolejne punkty. Ich pozycjonowanie jest zgodne z algorytmem rasteryzacji krzywych płaskich, więc fragmenty ogrodzenia mogą wystawać poza obszar ograniczony linią. W danej kratce może stać tylko jedno zabezpieczenie.

Punkty zostały podane w odpowiedniej kolejności. Dane są tak dobrane, aby zrasteryzowane linie się nie przecinały(mogą się nakładać). Ostatni punkt połączony jest z pierwszym. Czasem prezydent życzy sobie, aby zostało przygotowane miejsce wydzielone dla specjalnych gości.

Wejście

W pierwszej linii jedna liczba T(1<T<10³) oznaczająca liczbę testów. Dalej dla każdego testu jedna liczba N(2<N<10³) stanowiąca liczbę punktów ograniczających pole zabawy. Następnie są podane punkty w formacie X Y(0<X,Y<10⁹). Dane wejściowe są tak dobrane, że wynik nigdy nie przekroczy 8×10⁶.

Wyjście

Jedna liczba będąca sumą obwodów wewnątrz i zewnątrz zabezpieczeń.

Przyklad

Input:

2 
3 
2 3 
5 1 
8 5 
4 
1 1 
1 3 
3 3 
3 1

Output:

34 
16 

Wyjasnienie

Dla pierwszego testu obwód wew=10, zew=24

Dla drugiego testu obwód wew=4, zew=12

Uwaga! Zakłada się, że obwody są zawsze niezerowe.