К этой задаче прикреплён архив с материалами. Вы можете использовать его для моделирования и визуализации движения частиц.

VegiCat наблюдает за частицами на сетке из $n$ строк и $n$ столбцов. Левая нижняя клетка имеет координаты $(1, 1)$. Горизонтальная координата увеличивается слева направо, а вертикальная — снизу вверх. У каждой частицы есть горизонтальное направление (влево или вправо) и вертикальное направление (вверх или вниз). В начале каждого шага каждая частица корректирует свои направления следующим образом:

• Её горизонтальное направление меняется на противоположное, если следующая клетка в этом направлении находится за пределами сетки.
• Её вертикальное направление меняется на противоположное, если следующая клетка в этом направлении находится за пределами сетки.

После этих корректировок частица в клетке $(x, y)$ порождает две дочерние частицы:

• Одну в $(x - 1, y)$, если её горизонтальное направление — влево, или в $(x + 1, y)$, если вправо;
• Одну в $(x, y - 1)$, если её вертикальное направление — вниз, или в $(x, y + 1)$, если вверх.

Обе дочерние частицы наследуют горизонтальное и вертикальное направления родителя. После этого родительская частица исчезает.

Несколько частиц могут одновременно находиться в одной и той же клетке независимо от их направлений. Они никак не взаимодействуют и не меняют направления друг друга.

В момент времени $0$ в клетке $(x_0, y_0)$ находятся четыре частицы со следующими парами направлений:

• Вправо и вверх;
• Влево и вверх;
• Вправо и вниз;
• Влево и вниз.

На каждом шаге все частицы одновременно корректируют свои направления, а затем делятся, как описано выше.

Вам даны $q$ запросов. Каждый запрос задаёт целые числа $A, B, C$ и момент времени $t$. Для каждого запроса найдите количество клеток сетки $(x, y)$, которые удовлетворяют уравнению $Ax + By + C = 0$ и содержат хотя бы одну частицу в момент времени $t$.

Входные данные

Первая строка содержит целое число $T$ ($1 \le T \le 10^5$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит четыре целых числа $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$). Сетка состоит из $n$ строк и $n$ столбцов. Начальная клетка — $(x_0, y_0)$, а количество запросов равно $q$.

Каждая из следующих $q$ строк содержит четыре целых числа $A, B, C$ и $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Она описывает запрос для прямой $Ax + By + C = 0$ в момент времени $t$. Гарантируется, что $A$ и $B$ не равны $0$ одновременно.

Гарантируется, что сумма $q$ по всем наборам входных данных не превосходит $10^5$.

Выходные данные

Для каждого запроса выведите в отдельной строке одно целое число: количество клеток сетки $(x, y)$, которые удовлетворяют уравнению $Ax + By + C = 0$ и содержат хотя бы одну частицу в момент времени $t$.

Примеры

Входные данные 1

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

Выходные данные 1

1
0
0
3

Примечание

На рисунке ниже показана эволюция частиц в примере, а также запрашиваемые прямые, где серыми клетками обозначены клетки, содержащие целые точки, через которые проходит прямая, а все направления деления уже прошли корректировку допустимости. Поскольку третий запрос находится слишком далеко от рассматриваемой сетки, прямая третьего запроса здесь опущена.

Частицы в одной клетке с одинаковой парой направлений изображены одним символом; кратности опущены.