To zadanie posiada załącznik. Możesz go użyć do symulacji i wizualizacji ruchu cząstek.

VegiCat obserwuje cząstki na siatce o $n$ wierszach i $n$ kolumnach. Lewa dolna komórka ma współrzędne $(1, 1)$. Współrzędna pozioma rośnie od lewej do prawej, a współrzędna pionowa rośnie od dołu do góry. Każda cząstka ma kierunek poziomy (w lewo lub w prawo) oraz kierunek pionowy (w górę lub w dół). Na początku każdego kroku każda cząstka dostosowuje swoje kierunki w następujący sposób:

• Jej kierunek poziomy zostaje odwrócony, jeśli następna komórka w tym kierunku znajduje się poza siatką.
• Jej kierunek pionowy zostaje odwrócony, jeśli następna komórka w tym kierunku znajduje się poza siatką.

Po tych korektach cząstka znajdująca się w $(x, y)$ wytwarza dwie cząstki potomne:

• Jedną w $(x - 1, y)$, jeśli jej kierunek poziomy to lewo, lub w $(x + 1, y)$, jeśli to prawo;
• Jedną w $(x, y - 1)$, jeśli jej kierunek pionowy to dół, lub w $(x, y + 1)$, jeśli to góra.

Obie cząstki potomne dziedziczą kierunek poziomy i pionowy rodzica. Następnie rodzic znika.

Wiele cząstek może zajmować tę samą komórkę w tym samym czasie, niezależnie od swoich kierunków. Nie oddziałują one ze sobą ani nie zmieniają nawzajem swoich kierunków.

W chwili $0$ w komórce $(x_0, y_0)$ znajdują się cztery cząstki o następujących parach kierunków:

• Prawo i góra;
• Lewo i góra;
• Prawo i dół;
• Lewo i dół.

W każdym kroku wszystkie cząstki jednocześnie dostosowują swoje kierunki, a następnie dzielą się zgodnie z powyższym opisem.

Dane jest $q$ zapytań. Każde zapytanie podaje liczby całkowite $A, B, C$ oraz chwilę $t$. Dla każdego zapytania wyznacz liczbę komórek siatki $(x, y)$, które spełniają równanie $Ax + By + C = 0$ i zawierają co najmniej jedną cząstkę w chwili $t$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych. Poniżej znajduje się opis przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera cztery liczby całkowite $n, x_0, y_0, q$ ($2 \le n \le 10^9$, $1 \le x_0, y_0 \le n$, $1 \le q \le 10^5$). Siatka ma $n$ wierszy i $n$ kolumn. Komórka początkowa to $(x_0, y_0)$, a liczba zapytań wynosi $q$.

Każdy z kolejnych $q$ wierszy zawiera cztery liczby całkowite $A, B, C$ oraz $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Opisuje to zapytanie dla prostej $Ax + By + C = 0$ w chwili $t$. Gwarantuje się, że $A$ i $B$ nie są jednocześnie równe $0$.

Gwarantuje się, że suma $q$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego zapytania wypisz w osobnym wierszu jedną liczbę całkowitą: liczbę komórek siatki $(x, y)$, które spełniają $Ax + By + C = 0$ i zawierają co najmniej jedną cząstkę w chwili $t$.

Przykłady

Wejście 1

1
6 5 5 4
2 -1 -5 0
1 -1 0 1
11 45 14 2
1 0 -5 3

Wyjście 1

1
0
0
3

Uwaga

Poniższy rysunek przedstawia ewolucję cząstek w przykładzie oraz proste z zapytań, gdzie szare komórki oznaczają komórki zawierające punkty kratowe, przez które przechodzi prosta, a wszystkie kierunki podziału przeszły już korektę poprawności. Ponieważ trzecie zapytanie znajduje się zbyt daleko od rozważanej siatki, prosta z trzeciego zapytania została tutaj pominięta.

Cząstki znajdujące się w tej samej komórce i mające tę samą parę kierunków są narysowane jako pojedynczy symbol; krotności zostały pominięte.