До цієї задачі додається вкладення. Ви можете використати його для моделювання та візуалізації руху частинок.

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

Примітка

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

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