Este problema tiene un archivo adjunto. Puedes usarlo para simular y visualizar los movimientos de las partículas.

VegiCat observa partículas en una cuadrícula con $n$ filas y $n$ columnas. La celda inferior izquierda tiene coordenadas $(1, 1)$. La coordenada horizontal aumenta de izquierda a derecha, y la coordenada vertical aumenta de abajo hacia arriba. Cada partícula tiene una dirección horizontal (izquierda o derecha) y una dirección vertical (arriba o abajo). Al comienzo de cada paso, cada partícula ajusta sus direcciones de la siguiente manera:

• Su dirección horizontal se invierte si la siguiente celda en esa dirección está fuera de la cuadrícula.
• Su dirección vertical se invierte si la siguiente celda en esa dirección está fuera de la cuadrícula.

Después de estos ajustes, una partícula en $(x, y)$ produce dos partículas hijas:

• Una en $(x - 1, y)$ si su dirección horizontal es izquierda, o en $(x + 1, y)$ si es derecha;
• Una en $(x, y - 1)$ si su dirección vertical es abajo, o en $(x, y + 1)$ si es arriba.

Ambas partículas hijas heredan las direcciones horizontal y vertical de la partícula padre. Luego, la partícula padre desaparece.

Múltiples partículas pueden ocupar la misma celda al mismo tiempo, independientemente de sus direcciones. No interactúan ni cambian las direcciones de las demás.

En el tiempo $0$, hay cuatro partículas en $(x_0, y_0)$, con los siguientes pares de direcciones:

• Derecha y arriba;
• Izquierda y arriba;
• Derecha y abajo;
• Izquierda y abajo.

En cada paso, todas las partículas ajustan simultáneamente sus direcciones y luego se dividen como se describió anteriormente.

Se te dan $q$ consultas. Cada consulta proporciona enteros $A, B, C$ y un tiempo $t$. Para cada consulta, halla el número de celdas de la cuadrícula $(x, y)$ que satisfacen $Ax + By + C = 0$ y contienen al menos una partícula en el tiempo $t$.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^5$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene cuatro enteros $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 cuadrícula tiene $n$ filas y $n$ columnas. La celda inicial es $(x_0, y_0)$, y hay $q$ consultas.

Cada una de las siguientes $q$ líneas contiene cuatro enteros $A, B, C$ y $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Esto describe una consulta para la recta $Ax + By + C = 0$ en el tiempo $t$. Se garantiza que $A$ y $B$ no son ambos $0$ simultáneamente.

Se garantiza que la suma de $q$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada consulta, imprime un entero en una línea: el número de celdas de la cuadrícula $(x, y)$ que satisfacen $Ax + By + C = 0$ y contienen al menos una partícula en el tiempo $t$.

Ejemplos

Entrada 1

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

Salida 1

1
0
0
3

Nota

La figura de abajo muestra la evolución de las partículas en el ejemplo, así como las rectas consultadas, donde las celdas grises representan las celdas que contienen puntos enteros por los cuales pasa la recta, y todas las direcciones de división han pasado por los ajustes de validez. Dado que la tercera consulta está demasiado lejos de la cuadrícula considerada, la recta de la tercera consulta se omite aquí.

Las partículas en la misma celda con el mismo par de direcciones se dibujan como un único símbolo; las multiplicidades se omiten.