Questo problema ha un allegato. Puoi usarlo per simulare e visualizzare i movimenti delle particelle.

VegiCat osserva delle particelle su una griglia con $n$ righe e $n$ colonne. La cella in basso a sinistra ha coordinate $(1, 1)$. La coordinata orizzontale cresce da sinistra a destra, e la coordinata verticale cresce dal basso verso l'alto. Ogni particella ha una direzione orizzontale (sinistra o destra) e una direzione verticale (alto o basso). All'inizio di ogni passo, ciascuna particella regola le proprie direzioni come segue:

• La sua direzione orizzontale viene invertita se la cella successiva in quella direzione si trova fuori dalla griglia.
• La sua direzione verticale viene invertita se la cella successiva in quella direzione si trova fuori dalla griglia.

Dopo queste regolazioni, una particella in $(x, y)$ produce due particelle figlie:

• Una in $(x - 1, y)$ se la sua direzione orizzontale è sinistra, oppure in $(x + 1, y)$ se è destra;
• Una in $(x, y - 1)$ se la sua direzione verticale è basso, oppure in $(x, y + 1)$ se è alto.

Entrambe le particelle figlie ereditano la direzione orizzontale e verticale del genitore. Il genitore poi scompare.

Più particelle possono occupare la stessa cella contemporaneamente, indipendentemente dalle loro direzioni. Non interagiscono né modificano le direzioni le une delle altre.

Al tempo $0$, ci sono quattro particelle in $(x_0, y_0)$, con le seguenti coppie di direzioni:

• Destra e alto;
• Sinistra e alto;
• Destra e basso;
• Sinistra e basso.

A ogni passo, tutte le particelle regolano simultaneamente le proprie direzioni e poi si dividono come descritto sopra.

Ti vengono date $q$ query. Ciascuna query fornisce gli interi $A, B, C$ e un tempo $t$. Per ogni query, trova il numero di celle della griglia $(x, y)$ che soddisfano $Ax + By + C = 0$ e contengono almeno una particella al tempo $t$.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^5$), il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga di ogni caso di test contiene quattro interi $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$). La griglia ha $n$ righe e $n$ colonne. La cella iniziale è $(x_0, y_0)$, e ci sono $q$ query.

Ciascuna delle successive $q$ righe contiene quattro interi $A, B, C$ e $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Questo descrive una query per la retta $Ax + By + C = 0$ al tempo $t$. È garantito che $A$ e $B$ non sono entrambi $0$ contemporaneamente.

È garantito che la somma di $q$ su tutti i casi di test non supera $10^5$.

Output

Per ogni query, stampa un intero su una riga: il numero di celle della griglia $(x, y)$ che soddisfano $Ax + By + C = 0$ e contengono almeno una particella al tempo $t$.

Esempi

Input 1

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

Output 1

1
0
0
3

Nota

La figura sottostante mostra l'evoluzione delle particelle nell'esempio, insieme alle rette richieste nelle query, dove le celle grigie rappresentano le celle contenenti punti a coordinate intere attraversati dalla retta, e tutte le direzioni di divisione hanno subito le regolazioni di validità. Poiché la terza query è troppo lontana dalla griglia presa in considerazione, la retta della terza query è omessa qui.

Le particelle nella stessa cella con la stessa coppia di direzioni sono disegnate come un unico simbolo; le molteplicità sono omesse.