Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_27_05 - Taksówka na Manhattanie 6

Znany taksówkarz z Manhattanu - John Kowalsky ma nowy problem. Zastanawia się ile skrzyżowań znajduje się w zasięgu jego taksówki?

John mierzy odległość pomiędzy skrzyżowaniami w metryce Manhattan (jakże by inaczej), więc odległość pomiędzy dwoma punktami jest równa sumie wartości bezwględnych różnic ich współrzędnych. Dla wygody John przyjął taki układ współrzędnych, że ulice Manhattanu są równoległe od osi, a skrzyżowania znajdują się w punktach kratowych. Obszar po którym John jeździ ma kształt prostokąta wyznaczonego przez dwa skrzyżowania: to wysunięte najbardziej na południowy-zachód i znajdujące się w początku układu współrzędnych oraz to wysunięte najbardziej na północny-wschód o współrzędnych (N,M).

John znajduje się właśnie na jednym ze skrzyżowań w opisanym obszarze i ma w baku taksówki taką ilość paliwa, która wystarczy na przejechanie trasy o pewnej określonej długości. Ile skrzyżowań znajduje się w zasięgu taksówki Johna?

Wejście

W pierwszej linii liczba przypadków testowych t (≤ 100000).
W każdej z kolejnych t linii dane dla jednego testu w następującej postaci: 
Najpierw wymiary obszaru, po którym jeździ John jako dwie liczby całkowite N i M  (0 ≤ N, 109). Następnie kolejne dwie liczby całkowite x i y, określające współrzędne skrzyżowania, na którym obecnie John się znajduje (0xN, 0yM). Na koniec liczba całkowita k, oznaczająca maksymalną odległość, na jaką John może pojechać (0k109).

Wyjście

Dla każdego przypadku testowego, w osobnej linii, jedna liczba całkowita określająca liczbę skrzyżowań jakie znajdują się w zasięgu taksówki Johna.

Przykład

Wejście:
3
2 2 1 1 1
3 4 3 2 0 5 3 3 2 2
Wyjście:
5
1 12

Dodane przez:Witold Długosz
Data dodania:2016-04-25
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.